How do I check if two simple 2D arrays have the same 1D arrays? (order and repetitions doesn't matter)

Question

My main objective is to return if all elements, int[ ], of a 2D Array ,int[ ][ ], are present in another 2D Array.

I already tried to use Arrays.deepEquals() but in this case, the order of the elements would matter and that's not the purpose.

• Int[ ][ ] arrays wouldn't be longer than 15, for example.
• Int[ ][ ] arrays have always the same length.
• Int[ ][ ] arrays order doesn't matter, but Int[ ] arrays does.
• Int[ ] arrays would always be a pair.

Expected:

int[][] array1 = {{1, 2}, {2, 2}, {0, 1}, {3,4}} // Main Array

int[][] array2 = {{0, 1}, {2, 2}, {3,4} {1, 2}}} // Expected: true

int[][] array3 = {{6, 3}, {1, 2}, {7,4} {0, 1}}} // Expected: false
  

This is my solution/try:

// Check if an int[] array (element) belongs to an int[][] array.

public static boolean inVector(int[][] 2dArray, int[] 1dArray) {

    for (int i = 0; i < 2dArray.length; i++) {
        for (int j = 0; j < 2dArray[i].length; j++) {

            if (1dArray[0] == 2dArray[i][0] && 1dArray[1] == 2dArray[i][1]) {
                return true;
            }
        }
    }

    return false;
}


// Check if all int[] arrays of an int[][] belong to another int[][] array.

// This is not working properly

public boolean allBelongs() {

  boolean belongs = false;

  for (int i = 0; i < array1.length; i++) {
     
     if (inVector(array1, array2()[i])) {
        belongs = true;
     }
     
     else {
        belongs = false;
     }
  }

    return belongs;
}

EDIT: I solved the problem reversing the logic of the solution. Posted own answer.

Answer 1

You can use IntBuffer which can wrap an int[] array and provide the equals and hashCode implementations reflecting the array’s content.

public static boolean sameSubArrays(int[][] array1, int[][] array2) {
    if(array1 == array2) return true;
    HashSet<IntBuffer> set = new HashSet<>();
    for(int[] a: array1) set.add(IntBuffer.wrap(a));
    for(int[] a: array2) if(!set.contains(IntBuffer.wrap(a))) return false;
    return true;
}

This is simple and runs in linear time, hence, can cope with large arrays. It has the expected result for your test case.

int[][] array1 = {{1, 2}, {2, 2}, {0, 1}, {3,4}};
int[][] array2 = {{0, 1}, {2, 2}, {3, 4}, {1, 2}};
System.out.println(sameSubArrays(array1, array2)); // true

But it does not consider duplicates. If the number of occurrences must match for sub arrays with the same contents, you have to expand the solution to use a map to count the occurrences.

public static boolean sameSubArrays(int[][] array1, int[][] array2) {
    if(array1 == array2) return true;
    if(array1.length != array2.length) return false;
    HashMap<IntBuffer, Integer> map = new HashMap<>();
    for(int[] a: array1) map.merge(IntBuffer.wrap(a), 1, Integer::sum);
    for(int[] a: array2)
        if(map.merge(IntBuffer.wrap(a), -1, Integer::sum) < 0) return false;
    return true;
}

Since your example has no duplicates, it still has the same result.

Answer 2

This solution should work. If the arrays are relatively small (for example, 2 by 4), it will likely be faster than other solutions:

import java.util.Arrays;

class Main {
  public static boolean isSubarrayUnordered(int[][] child, int[][] parent) {
    for (int[] childSubarray : child) {
      boolean found = false;
      for (int[] parentSubarray : parent) {
        if (Arrays.equals(childSubarray, parentSubarray)) {
          found = true;
          break;
        }
      }
      if (!found) return false;
    }
    return true;
  }

  public static void main(String[] args) {
    int[][] array1 = {{1, 2}, {2, 2}, {0, 1}, {3, 4}};
    int[][] array2 = {{0, 1}, {2, 2}, {3, 4}, {1, 2}};
    int[][] array3 = {{1, 2}, {2, 2}, {0, 999}, {3, 4}};

    System.out.println("array1 in array2? " + isSubarrayUnordered(array1, array2));
    System.out.println("array1 in array3? " + isSubarrayUnordered(array1, array3));
  }
}

For medium-sized arrays (maybe hundreds to thousands of total elements), it might be faster to create sorted copies of both arrays, and have two iterators over both arrays itChild, itParent. For each element of itChild, if the current element of itParent is equal (using Arrays.equals, then advance both itChild and itParent. Otherwise, advance only itParent. Repeat until there are either no more elements in itChild (return true) or no more elements in itParent (return false).

For extremely large arrays (millions to billions of elements), the costs of creating a copy may be prohibitively expensive. You will probably want to create a compressed representation of the array using something like a sha256 hash, and then compare only the hashes of the elements. This has a small probability of returning the wrong answer though, if the array is extremely large.

Answer 3

Instead of verifying if ALL int[] are present in the int[][], I can just verify if ONE int[] isn't present.

public boolean allBelongs() {

  for (int i = 0; i < array1.length; i++) {
 
    if (!inVector(array1, array2()[i])) {
       return false;
    }
  }

  return true;
}