Java, How to check if two 2d arrays contain the same values

Question

I need to check if two 2 dimensional arrays of [5][5] contain the same values even if one is shuffled.

I need the method to return true if the two arrays contain the same values even if that are arranged in a different way like:

• 1,2,3,4,5
• 6,7,8,9,10
• 11,12,13,14,15
• 16,17,18,19,20
• 21,22,23,24,25

And:

• 25,24,23,22,21
• 1,2,3,4,5,
• 7,8,9,10,6
• 20,19,18,17,16
• 15,14,13,12,11

What is the best way to return true when both have the same values?

Answer 1

Here is my solution. Rather simple to use.

int[][] array1 = {
    {1,2,3,4,5},
    {6,7,8,9,10},
    {11,12,13,14,15},
    {16,17,18,19,20},
    {21,22,23,24,25}
};

int[][] array2 = {
    {25,24,23,22,21},
    {1,2,3,4,5},
    {7,8,9,10,6},
    {20,19,18,17,16},
    {15,14,13,12,11}
};

sort2D(array1);
sort2D(array2);

System.out.println(Arrays.deepEquals(array1, array2));

Which prints true in this case.

The method sort2D is implemented as follows:

public static void sort2D(int[][] array) {
    for (int[] arr : array) {
        Arrays.sort(arr);
    }

    Arrays.sort(array, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return new BigInteger(Arrays.toString(o1).replaceAll("[\\[\\], ]", ""))
                .compareTo(new BigInteger(Arrays.toString(o2).replaceAll("[\\[\\], ]", "")));
        }
    });
}

You can optimise it further by precompiling the regex but basically, you should get the idea.

Answer 2

If you need a very efficient algorithm for determining list/array equivalence, where the two lists/arrays contain the same number of items but not necessarily in the same order, try the algorithm below. I learned it from this stack overflow question/answers and it's great!

boolean AreEquivalent(int[][] arrayOne, int[][] arrayTwo) {
  Dictionary<int, int> valueMap = new Dictionary<int, int>();

  // Add one for each occurrance of a given value in the first array
  for(int i=0; i<5; i++)
  for(int j=0; j<5; j++)
  {
    if (valueMap.containsKey(arrayOne[i][j]))
    {
      valueMap[arrayOne[i][j]]++;
    }
    else
    {
      valueMap[arrayOne[i][j]] = 1;
    }
  }

  // subtract one for each occurrance of a given value in the second array
  for(int i=0; i<5; i++)
  for(int j=0; j<5; j++)
  {
    if (valueMap.containsKey(arrayTwo[i][j]))
    {
      valueMap[arrayOne[i][j]]--;
    }
    else
    {
      // We can short circuit here because we have an item in the second
      // array that's not in the first array.
      return false;
    }
  }

  // now check the final tally, if not 0 the two arrays are not equivalent
  for (int tally: valueMap.values())
  {
    if (tally != 0)
    {
      return false;
    }
  }

  return true;
}

Answer 3

Here's an example for what MaxMackie suggested. I'm converting the array to a list because to compare 2x 2d arrays you'd need 4 cycles, 2 for the 1st array and 2 for the 2nd.

// to list
ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<Integer> list2 = new ArrayList<Integer>();
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        list1.add(array1[i][j]);
        list2.add(array2[i][j]);
    }
}

// comparing
boolean isInBoth;
for (int i = 0; i < 25; i++) { // 1st list
    isInBoth = false;
    for (int j = 0; j < 25; j++) { // 2nd list
        if (!isInBoth) { // if not found number in 2nd array yet
            if (list1.get(i) == list2.get(j)) { // if numbers are equal
                isInBoth = true; 
            }
        }
    }

    if (!isInBoth) { // if number wasn't in both lists
        return; 
    }
}

if (isInBoth) {
    System.out.println("Arrays are equal");
}

Answer 4

I suggest you sort those arrays first. If you don't want the values to move, you can simply create copies of the existing arrays and work with the copies.

Here's my code for this problem: (It sorts without the use of lists)

public class TwoDArraySort 
{
static int[][] arr1 = {{1,2,3,4,5}, {6,7,8,9,10}, {11,12,13,14,15}, {16,17,18,19,20}, {21,22,23,24,25}};
static int[][] arr2 = {{25,24,23,22,21}, {1,2,3,4,5}, {7,8,9,10,6}, {20,19,18,17,16}, {15,14,13,12,11}};

public static void main(String[]args) //The code below is meant to sort the second array
{
    int lowest;
    int switcher;
    int posX = -1;
    int posY = -1;

    for (int i=0; i<arr2.length; i++)
    {
        for (int z=0; z<arr2[i].length; z++)
        {
            lowest = arr2[i][z];

            for (int x=i; x<arr2.length; x++)
            {
                if (x == i)
                    for (int y=z; y<arr2[x].length; y++)
                    {
                        if (arr2[x][y] <= lowest)
                        {
                            lowest = arr2[x][y];
                            posX = x;
                            posY = y;
                        }
                    }
                else
                    for (int y=0; y<arr2[x].length; y++)
                    {
                        if (arr2[x][y] <= lowest)
                        {
                            lowest = arr2[x][y];
                            posX = x;
                            posY = y;
                        }
                    };
            }
            switcher = arr2[i][z];
            arr2[i][z] = arr2[posX][posY];
            arr2[posX][posY] = switcher; //Switches the lowest value to the first position that hasn't been changed already
        }
    }

    System.out.println(isSame(arr1, arr2)); //Calls the isSame method and print the returned boolean
}

//This method returns true if the arrays are the same
public static boolean isSame(int[][] arr1, int[][] arr2)
{
    for (int x=0; x<arr1.length; x++)
    {
        for (int y=0; y<arr1[x].length; y++)
        {
            if (arr1[x][y] != arr2[x][y])
            {
                return false;
            }
        }
    }

    return true;
}
}

Hope this helps you

Answer 5

If it doesn't matter if data in rows are the same, but shuffled we can just store all numbers from arrays into separate Lists and then compare them.

int[][] a1 = { { 1, 2 }, { 3, 4 } };
int[][] a2 = { { 4, 3 }, { 2, 1 } };

//lists to store arrays data
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();

//lest place data from arrays to lists
for (int[] tmp:a1)
    for (int i:tmp)
        list1.add(i);

for (int[] tmp:a2)
    for (int i:tmp)
        list2.add(i);

//now we need to sort lists
Collections.sort(list1);
Collections.sort(list2);

//now we can compare lists on few ways

//1 by Arrays.equals using list.toArray() 
System.out.println(Arrays.equals(list1.toArray(), list2.toArray()));
//2 using String representation of List
System.out.println(list1.toString().equals(list2.toString()));
//3 using containsAll from List object
if (list1.containsAll(list2) && list2.containsAll(list1))
    System.out.println(true);
else 
    System.out.println(false);

//and many other probably better ways

---

If rows also have to contain same numbers (but can be shuffled like [1,2] [2,1] but not like [1,2][1,3]) you can do something like this

// lets say i a1 and a2 are copies or original arrays 
int[][] a1 = { { 1, 2 }, { 3, 4 } };
int[][] a2 = { { 4, 3 }, { 2, 1 } };
System.out.println(Arrays.deepToString(a1));// [[1, 2], [3, 4]]
System.out.println(Arrays.deepToString(a2));// [[3, 4], [1, 2]]

// lets sort data in each row
for (int[] tmp : a1)
    Arrays.sort(tmp);
for (int[] tmp : a2)
    Arrays.sort(tmp);
System.out.println("========");
System.out.println(Arrays.deepToString(a1));// [[1, 2], [3, 4]]
System.out.println(Arrays.deepToString(a2));// [[3, 4], [1, 2]]

// Now I want to order rows by first stored number.
// To do that I will use Array.sort with this Comparator
Comparator<int[]> orderByFirsNumber = new Comparator<int[]>() {
    public int compare(int[] o1, int[] o2) {
        if (o1[0] > o2[0]) return 1;
        if (o1[0] < o2[0]) return -1;
        return 0;
    }
};

// lets sort rows by its first stored number
Arrays.sort(a1, orderByFirsNumber);
Arrays.sort(a2, orderByFirsNumber);

// i wonder how arrays look 
System.out.println("========");
System.out.println(Arrays.deepToString(a1));// [[1, 2], [3, 4]]
System.out.println(Arrays.deepToString(a2));// [[1, 2], [3, 4]]

System.out.println("Arrays.deepEquals(a1, a2)="
        + Arrays.deepEquals(a1, a2));

Output

[[1, 2], [3, 4]]
[[4, 3], [2, 1]]
========
[[1, 2], [3, 4]]
[[3, 4], [1, 2]]
========
[[1, 2], [3, 4]]
[[1, 2], [3, 4]]
Arrays.deepEquals(a1, a2)=true