Take the 2-minute tour ×

What is the best approach to solve the following problem in Java? There are 3 two-dimensional arrays that have equal number of rows and columns:

[1]: {1, 2, 3}
[2]: {2, 2, 4}
[3]: {1, 1, 1}

[1]: {1, 2, 0}
[2]: {1, 2, 3}
[3]: {1, 0, 1}

[1]: {1, 1, 1}
[2]: {1, 2, 3}
[3]: {1, 0, 1}

I need to find out the indexes of rows that exist in all arrays. In the above example the answer should be: [1],[2],[2]

Array1 [1]: {1, 2, 3}

Array2: [2]: {1, 2, 3}

Array3: [2]: {1, 2, 3}

UPDATE: Is there any built-in function to do this? Or is the FOR loop the unique solution?

share|improve this question

6 Answers 6

up vote 1 down vote accepted

I would do the following:

  • Create a class that takes a row in the array and implements hashcode and equals.
  • Insert each row (wrapped in the above class) in the first two arrays into two HashMaps
  • for each row in the last array, determine if they exist in the HashMaps

Edit #2, realized the mapping would need to be reversed.

private Map<MyClass, Integer> map(int[] array){
  Map<MyClass, Integer> arrayMap = new HashMap<>();
  for (int i; i<array.length; i++)
        arrayMap.put(new MyClass(array[i]), i);

private mySearch(){
   int[] array1, array2, array3;

   Map<MyClass, Integer> map1 = map(array1);
   Map<MyClass, Integer> map2 = map(array2);

   for (int i=0; i<array3.lenght; i++){
      MyClass row = new MyClass(array3[i]);
      Integer array1Row = map1.get(row);
      Integer array2Row = map2.get(row);

      if (array1Row != null && array2Row != null){
         // Matching rows found
share|improve this answer
Could you please give an example of the second step? –  Klausos Klausos Jan 9 '12 at 12:22
It will work for any number of arrays, right? –  Klausos Klausos Jan 9 '12 at 13:37
Yes. 11 more to go... –  John B Jan 9 '12 at 13:38

AFAIK there is no built-in function for this.

You need to write your own function to implement it (using for loop).

post some code to show what have you tried, if it's not working corectly OR for optimization.

share|improve this answer

Check this code:

ArrayList<Integer[]> arr1 = new ArrayList<Integer[]>();
    arr1.add(new Integer[]{1,2,3});
    arr1.add(new Integer[]{2,2,5});
    arr1.add(new Integer[]{1,1,1});

    ArrayList<Integer[]> arr2 = new ArrayList<Integer[]>();
    arr2.add(new Integer[]{1,2,0});
    arr2.add(new Integer[]{1,2,3});
    arr2.add(new Integer[]{1,0,1});

    ArrayList<Integer[]> arr3 = new ArrayList<Integer[]>();
    arr3.add(new Integer[]{1,1,1});
    arr3.add(new Integer[]{1,2,3});
    arr3.add(new Integer[]{1,0,1});

    for (int r = 0 ; r < arr1.length() ; r++) {
        for(int s = 0 ; s < arr2.length() ; s++){
            for(int t = 0 ; t < arr3.length() ; t++){
                if(Arrays.deepEquals(arr1.get(r), arr2.get(s))){

                if(Arrays.deepEquals(arr1.get(r), arr3.get(t))){
                    System.out.println(r + " " + s + " " +t);;  

share|improve this answer
Will it work if the number of rows is different in each array? –  Klausos Klausos Jan 9 '12 at 12:58
Also, if the number of arrays is greater than 3, will it work? –  Klausos Klausos Jan 9 '12 at 12:59
It will work with any number of rows in the arrays, just update the loop indicies. However, this is the least efficient solution possible O(n^3). Mike's solution is at least more efficient than this. I think hash solution is even better. –  John B Jan 9 '12 at 13:11

First of all, write a function called AreRowsEqual(), which compares two rows. So, now, the problem has been restated as Find similar elements in 3 arrays.

Secondly, try to think of a solution that would be the closest to something you already know based on prior knowledge: to find equal elements in two arrays, you need a double nested for loop. So, to find equal elements in three arrays, you would need a triple nested loop, right?

Okay, now, cross this out as a bad, bad, bad solution, because its time complexity is O(n^3). We should be able to do better.

Consider this: in order for an element to be similar in all 3 arrays, first it has to be similar among the first two; then, it has to be similar among the next two. The complexity of such an algorithm will be something akin to O(x*n), where x is the number of arrays. Much better, right? (I cannot figure out precisely what the O() will be, help anyone?) EDIT: it turns out it is O((n^2)*(x-1)), which is a lot better than O(n^3) when n > x --END EDIT This, incidentally, allows you to forget about the requirement for strictly 3 arrays and just consider a number of x arrays.

I wrote an approach which received one upvote and then I realized that it was not going to work and I deleted it. This is another try, which I believe will work:

Create a two dimensional array of integers. We will call this 'the matrix'. This matrix will have x columns, and the number of rows will be the number of rows of your first array. (Yes, this will work even if your arrays have differing lengths.) The numbers in the cells of this matrix will be matching row indexes. So, for example, after the algorithm I am describing finishes, a row of { 1, 3, 2 } in the matrix will tell us that row 1 of the first array matches row 3 of the second array and row 2 of the third array. We will use -1 to indicate 'no match'.

So, the first column of the matrix needs to be initialized with the indexes of all rows of your first array, that is, with the numbers 0, 1, 2, ... n where n is the number of elements in the first array.

For each additional array, fill its column in the matrix as follows: loop through each row of the current column in the matrix, and compute the cell as follows: if the corresponding cell of the previous column was -1, carry the -1 over into this cell. Otherwise, look for a row in the current array which matches the corresponding row of the previous array, and if found, store its index into this cell. Otherwise, store -1 in this cell.

Repeat for all of your arrays, that is, for all the columns in the matrix. In the end, your matching rows are those that do not have a -1 in the last column of the matrix.

If you really care about efficiency, you can do as John B suggested, and write an immutable class called Row which encapsulates (contains a reference to) a row and implements hashCode() and equals(). equals() here can be implemented using Arrays.deepEquals(). There may also be some goodie in Arrays called deepHashCode(), or else you will need to roll your own.

share|improve this answer
And if the number of rows is different in arrays, will the solution be approximately the same? –  Klausos Klausos Jan 9 '12 at 12:10
-1 Comparison of first two arrays would be O(n^2) so overall time would be greater than that not O(x*n) as suggested. –  John B Jan 9 '12 at 13:04
I wrote an approach which received one upvote and then I realized that it was not going to work and I deleted it. I have now posted another try, which I believe will work. –  Mike Nakis Jan 9 '12 at 13:12
@JohnB I updated my answer. My previous answer perhaps deserved a downvote because it would not work, but not because of such a minute detail as a wrong estimate of what its big-oh would be. The algorithm I am presenting certainly does better than O(n^3). I still cannot figure exactly what its big-oh is, so please feel free to help me figure it out. –  Mike Nakis Jan 9 '12 at 13:20
@MikeNakis removed down vote. In the worst case scenario (all rows of the first x-1 arrays match), the above would be O(n^3). The actual performance would depend on the number of matches at each array. IMHO the hashing solution is simpler and more efficient so I appreciate the reference. –  John B Jan 9 '12 at 13:26
  1. Write a method that accepts two arguments: a two dimensional array to search for, a one dimensional array row. The method returns -1 if no match found, otherwise return the index of the matching row.

  2. For each row of the first array: 2a. Call the method passing the row from first array and Array2. 2b. If 2a returns >0, call the method passing the same row and Array3

  3. If 2b returns >0, output the returned indexes.

share|improve this answer
two issues: first should be >=0. Second, this is inefficient, at least O(n^2) if not closer to O(n^3). If every row in array 1 exists is array 3, this would be O(n^3). Hashing is a better alternative imho. –  John B Jan 9 '12 at 12:17

Check Arrays.deepEquals() method. It will check two arrays are equal or not.

share|improve this answer
This is a good way to determine matches, but the alg would be O(n^2) –  John B Jan 9 '12 at 12:04
No, that won't work, because the rows are not guaranteed to be in the same order. Row [1] in one array may match row [2] in another array, but deepEquals() would not consider this as a match. –  Mike Nakis Jan 9 '12 at 12:10

Your Answer


