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

Answer 1

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);
        }
    }
}

Answer 2

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]

Answer 3

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.

Answer 4

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

Answer 5

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());
}