2

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.

tnrodrigues
  • 23
  • 6
  • 1
    Do you have specific performance requirements? How large do you expect the arrays to be? – Brandon Jan 07 '22 at 03:19
  • 1
    For example, if the arrays are typically very small, the simplest and fastest solution is probably a nested loop that loops over each subarray A in the first array, and then for each subarray B in the second array, checks whether A deepequals B, and if that is the case for each A, return true, otherwise return false – Brandon Jan 07 '22 at 03:24
  • No, I do not have any performance requirements. – tnrodrigues Jan 07 '22 at 10:13
  • Int[ ] arrays would always be a pair. :) – tnrodrigues Jan 07 '22 at 10:31
  • I'm expecting the int[ ] [ ] arrays to do not have a bigger length than 15, for example. – tnrodrigues Jan 07 '22 at 10:34

3 Answers3

4

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.

Holger
  • 285,553
  • 42
  • 434
  • 765
  • Does your first snippet check if they are equal, or just that array2 is a subset of array1? Looks like it would return true for non-empty array1 and empty array2. – Andy Turner Jan 07 '22 at 10:46
  • 1
    @AndyTurner the first snippet checks whether all sub arrays of `array2` are also sub arrays of `array1`. You could augment it with a length check, but it still wouldn’t handle duplicates, so even then, `array2` could consist of just repetitions of one sub-array only. So for a “contains all of the other array” check, you’d have to use the second snippet. – Holger Jan 07 '22 at 11:01
  • Thank your for your answer Holger. I think this is the most simple and correct approach. – tnrodrigues Jan 07 '22 at 15:31
1

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.

Brandon
  • 1,336
  • 3
  • 10
  • 38
  • 1
    Why are you using boxed `Boolean` in your method? Note that you are thinking too complicated for larger arrays; there is [a much simpler solution](https://stackoverflow.com/a/70618387/2711488). – Holger Jan 07 '22 at 08:21
  • There's no reason for the boxed `Boolean`, edited my answer to remove it. – Brandon Jan 07 '22 at 15:14
  • "you are thinking too complicated" -- under the hood, `IntBuffer` in your linked solution is using `hashCode` for efficient `equals` comparison, so the core idea is not complicated. Also, if the data is extremely large, then sha256 is going to be much faster than IntBuffer, because in the case where elements _are_ equal you have to compare each element. If the array is M X N (size N subarrays) then each equality check is O(N) vs O(1) with sha256. But yes, I agree that `IntBuffer` is a nice simple solution. – Brandon Jan 07 '22 at 15:20
  • 1
    Thank you for your answer Brandon. It helped me figuring out that with a different approach I could solve the problem, Instead of verifying if ALL `int[]` are present in the `int[][]`, I could just verify if ONE `int[]` isn't present. – tnrodrigues Jan 07 '22 at 15:28
  • 1
    To calculate an sha256, you have to go over the entire array anyway and since an equal hash does not prove that the array is equal (for a large array), you also have to compare the elements. – Holger Jan 07 '22 at 17:04
0

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;
}
tnrodrigues
  • 23
  • 6