Collect indexes of duplicates values in 2D int array algorithm

Question

I'm working on slot machine and faced the problem of collecting outcomes results. Question is what is the fastest approach to collect indexes of duplicate values in 2D int array? Condition here is to collect only idexes of values which occur 5 times

CASE 1

input (get indexes of 3 value only):

int[][] input = new int[][]{
 new int[]{1, 2, 3, 4, 8},
 new int[]{6, 3, 2, 3, 5},
 new int[]{3, 9, 7, 1, 3}
 };

expected output:

[2, 1, 0, 1, 2]

CASE 2

input (get indexes of 3 and 5 values only):

int[][] input = new int[][]{
 new int[]{1, 5, 3, 5, 8},
 new int[]{5, 3, 5, 3, 5},
 new int[]{3, 9, 7, 1, 3}
 };

expected output:

[2, 1, 0, 1, 2] //for 3 value
[1, 0, 1, 0, 1] //for 5 value

MY SOLUTION(its quite poor)

1) gather duplicates (this one not working for CASE 2)

Map<Integer, Integer> amountMap = new HashMap<>();
for (int[] row : railSpin) {
 for (int value : row) {
 amountMap.put(value, amountMap.containsKey(value) ? amountMap.get(value) + 1 : 1);
 }
}

2) remove non 5 matches

if (amountMap.containsValue(5)) {
 Iterator<Integer> amountIterator = amountMap.values().iterator();
 while (amountIterator.hasNext()) {
 if (amountIterator.next() != 5) {
 amountIterator.remove();
 }
 }
}

3) iterate upside-down and collect indexes

List<Integer> indexes = new ArrayList<>();
for (int row = 0; row < 5; row++) {
 for (int col = 0; col < railSpin.length; col++) {
 int valueToCheck = railSpin[col][row];
 if (amountMap.keySet().contains(valueToCheck)) {
 indexes.add(col);
 }
 }
}

4) split array if needed

List<List<Integer>> splitResults = new ArrayList<>();
for (int start = 0; start < indexes.size(); start += 5) {
 int end = Math.min(start + 5, indexes.size());
 List<Integer> sublist = indexes.subList(start, end);
 splitResults.add(new ArrayList<>());
 splitResults.get(start /5).addAll(sublist);
}

Can you suggest a solution without so many iterations and which would be suitable for CASE 2? I belive in power of stackoverflow

• Sergey Kalinichenko: I assume your 2D array is of fixed size 5 by 3, right? Also the numbers are in the range from 1 to 9?
• AnZ: @dasblinkenlight that's right. Although I'm trying to create versatile algorithm for both 5x3 and 3x3 2D arrays. Height is contstant but width might differ

Answer 1

How I'd do it :

1. Iterate over the whole table ONCE in order to create a Map of indexes
2. Remove any entry which has not 5 valid indexes

EDIT : I switched to working with ArrayList because it's simply better :

Code :

public static void main(String t[]) throws IOException {
 int[][] input1 = new int[][] { 
 new int[] { 1, 2, 3, 4, 8 },
 new int[] { 6, 3, 2, 3, 5 },
 new int[] { 3, 9, 7, 1, 3 } };
 int[][] input2 = new int[][] { 
 new int[] { 1, 5, 3, 5, 8 }, 
 new int[] { 5, 3, 5, 3, 5 },
 new int[] { 3, 9, 7, 1, 3 } };
 System.out.println("case 1");
 doWith(input1);
 System.out.println("case 2");
 doWith(input2);
}
public static void doWith(int[][] table){
 Map<Integer, List<Integer>> allIndexes = getAllIndexes(table);
 /* Java 8 style
 Map<Integer, List<Integer>> fiveOccurrencesIndexes = allIndexes.entrySet().stream()
 .filter(e ->e.getValue().size() == ROW_SIZE)
 .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
 */
 Map<Integer, List<Integer>> fiveOccurrencesIndexes = new HashMap<Integer,List<Integer>>();
 for(Map.Entry<Integer,List<Integer>> entry : allIndexes.entrySet()){
 if(entry.getValue().size() == ROW_SIZE){
 fiveOccurrencesIndexes.put(entry.getKey(), entry.getValue());
 }
 }
 fiveOccurrencesIndexes.entrySet().forEach(e -> System.out.println(e.getKey()+ " : "+e.getValue()));
}
// Map of indexes per value
public static Map<Integer,List<Integer>> getAllIndexes(int[][] table){
 Map<Integer,List<Integer>> result = new HashMap<>();
 // we should force minValue < maxValue
 for(int i=0; i<ROW_SIZE; i++){ 
 for(int j=0;j<COL_SIZE; j++){
 Integer value = table[j][i];
 if(!result.containsKey(value)){ 
 List<Integer> indexes = new ArrayList<>(); // init value
 result.put(value, indexes);
 }
 result.get(value).add(j);
 }
 }
 return result;
}

Output :

case 1
3 : [2, 1, 0, 1, 2]
case 2
3 : [2, 1, 0, 1, 2]
5 : [1, 0, 1, 0, 1]

• AnZ: I like this solution but can you make some edit to make it appliable for pre 24 API level? Streams re not supported for lower levels
• AnZ: I mean, cou you use Java 7 only?
• AnZ: thank you for the edit! Both your variants work like a charm! I like your answer the most because of its sharpness and pithiness. Also you did great job for covering both Java 7 and 8. Million thanks.
• Jeremy Grand: Thanks for the comment, but I have to admit that I don't like very much the idea of working with 2D arrays and returning indexes as another Array. My code here is wasting a lot of allocations to fill the arrays with -1. I should edit it again to use arrayLists instead. And I think you'd gain a lot by using an OO pattern instead of a int[][]
• Jeremy Grand: Because if I'm working with ArrayList (whose size can vary) instead of arrays, I can avoid to fill the arrays with -1 (N less operations) and simply check the lists' size instead of iterating over the arrays again to check the absence of -1. And the code is shorter. :)

Answer 2

I think it's hard to get rid of these loops, but you can make it work for case 2 as shown below:

// Gather duplicates
Map<Integer, Integer> amountMap = new HashMap<>();
for (int[] row : railSpin) {
 for (int value : row) {
 amountMap.put(value, amountMap.containsKey(value) ? amountMap.get(value) + 1 : 1);
 }
}
// Create index list for 5 matches
HashMap<Integer,List<Integer>> resultsMap = new HashMap<Integer,List<Integer>>();
if (amountMap.containsValue(5)) {
 for( Integer key : amountMap.keySet()) {
 if (amountMap.get( key) == 5) {
 resultsMap.put( key, new ArrayList<Integer>());
 }
 }
}
// For all 5 matches, collect indices
List<Integer> indexList;
for( Integer index : resultsMap.keySet())
{
 indexList = resultsMap.get( index);
 for (int row = 0; row < 5; row++) {
 for (int col = 0; col < railSpin.length; col++) {
 if (railSpin[col][row] == index) {
 indexList.add(col);
 }
 }
 }
}
// Print
StringBuilder sb;
for( Integer index : resultsMap.keySet())
{
 sb = new StringBuilder();
 indexList = resultsMap.get( index);
 for( Integer i : indexList) {
 if( sb.length() == 0) {
 sb.append( "[");
 } else {
 sb.append( ", ");
 }
 sb.append( i.intValue());
 }
 sb.append( "]");
 System.out.println( sb.toString());
}

• AnZ: oh, you fixed my mistake. Thank for your answer. It works but I have to give my vote for the more sophisticated solution

Answer 3

Update: removed option 2 since it was flawed and merged both options into one solution.

On 2D arrays, there is always the option to avoid at least one nested iteration, by reducing them to a 1D array and specific the (implicit) width of the row:

int[] input = new int[]{1, 2, 3, 4, 8, 6, 3, 2, 3, 5, 3, 9, 7, 1, 3};
int gridWidth = 5;

You then need only one iteration for all values. But you also need supporting functions to get the current value's 2D index (x,y):

public static int get_y(int index, int gridWidth) {
 return floor((index / gridWidth));
}
public static int get_x(int index, int gridWidth){
 return index % gridWidth;
}

You can then go through all your values for one time and add them to an index HashMap and count them up on a counter hash map.

HashMap<Integer, int[]> counts = new HashMap<Integer, int[]>();
HashMap<Integer, Integer> times = new HashMap<Integer, Integer>();
//iterate once through all values
for (int i = 0; i < input.length; i++) {
 // get position in input
 int x = get_x(i, gridWidth);
 int y = get_y(i, gridWidth);
 int value = input[i];
 // add indices for this number
 // or create new indices array
 int[] indices = counts.get(value);
 if (indices == null) {
 indices = new int[gridWidth];
 for (int j = 0; j< gridWidth; j++) {
 //initialze indices with -1 as default
 indices[j] = -1;
 times.put(value, 0); //count counter
 }
 }
 // assign values
 // +1 because 0 means not present
 indices[x] = y;
 counts.put(value, indices);
 // counting up
 int counter = times.get(value);
 times.put(value, counter +1);
 }

Use indices arrays with fixed width and initial entries of -1 to distinct, which positions occurred or not while not confuse the 0 positions. Content of the HashMap for the input is:

 1 count: 2
[0] 0
[1] -1
[2] -1
[3] 2
[4] -1
2 count: 2
[0] -1
[1] 0
[2] 1
[3] -1
[4] -1
3 count: 5
[0] 2
[1] 1
[2] 0
[3] 1
[4] 2
4 count: 1
[0] -1
[1] -1
[2] -1
[3] 0
[4] -1
5 count: 1
[0] -1
[1] -1
[2] -1
[3] -1
[4] 1
6 count: 1
[0] 1
[1] -1
[2] -1
[3] -1
[4] -1
7 count: 1
[0] -1
[1] -1
[2] 2
[3] -1
[4] -1
8 count: 1
[0] -1
[1] -1
[2] -1
[3] -1
[4] 0
9 count: 1
[0] -1
[1] 2
[2] -1
[3] -1
[4] -1

From here you can further process the data on all your needs. Both approaches still require some additional iteration (Option 1: for loop for new indices, Option 2: underlying computation ArrayList add operations) but I hope this may satisfy your needs.

Advantages of this approach:

• all indices are generated in one iteration (fitting the "wheel" behavior)
• scalable to a certain degree (number of wheels etc.)
• splitting of counting and occurrences into separate maps for lightweight requests on counting

• AnZ: thanks for your answer. It seem to be working although there's additional need in checking for matches from times to counts. And 3 level iteration... I belive Jeremy's answer better. Although thanks for your time.
• Jankapunkt: Hi AnZ, no problem. When your application grows in complexity, just keep in mind there is a scalable solution here, too. Happy coding :-)

Answer 4

First, find all numbers that are present five or more times:

int[] counts = new int[10];
for (int r = 0 ; r != 3 ; r++)
 for (int c = 0 ; c != 5 ; c++)
 counts[input[r][c]]++;

Now use counts to produce index arrays (this is pretty much a re-arrangement of combined steps (3) and (4) from your algorithm):

List<List<Integer>> splitResults = new ArrayList<>();
for (int num = 0 ; num != 10 ; num++) {
 if (counts[num] < 5) {
 continue;
 }
 List<Integer> toAdd = new ArrayList<>();
 for (int c = 0 ; c != 5 ; c++) {
 for (int r = 0 ; r != 3 ; r++) {
 if (input[r][c] == num) {
 toAdd.add(r);
 break;
 }
 }
 }
 splitResults.add(toAdd);
}

Demo.

• AnZ: this one doesn't seem to be working. splitResults has 2 lists with the same ascending integers from 0 to 4. Also I'm not sure if a 3 level iteration is a good idea..
• Sergey Kalinichenko: @AnZ That's because I was adding c instead of r. This is now fixed (see demo). As far as the third level of iteration goes, it's not really a third level, because in most cases it is cut short by continue. The outer loop will never run its "payload" more than three times.

Answer 5

Here is one of short solutions:

final Map<Integer, List<Integer>> res = new HashMap<>();
final Map<Integer, Long> occursMap = Stream.of(input).flatMapToInt(e -> IntStream.of(e)).boxed()
 .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
for (int j = 0; j < input[0].length; j++) {
 for (int i = 0; i < input.length; i++) {
 if (occursMap.getOrDefault(input[i][j], 0L) == 5) {
 res.computeIfAbsent(input[i][j], ArrayList::new).add(i);
 }
 }
}