0

I'm working on a beginner question that checks if one array is the subset of another array, and I got stuck on one special case, here is the case example: a = [1,2,3], b = [1,1], in which a contains 1, b only contains 1, but b is not a subset of a because b contains two of 1s.

How can I modify my code to have it check this special case?

Below is the code snippet:

// True if one array is the subset of another array
public boolean checkSubset(int[] arr1, int[] arr2) {
    // A counter to remember how many
    // times the same element is found
    int cnt = 0;

    // If one of the array is empty, for empty set
    if (arr1.length == 0 || arr2.length == 0) {
        return true;
    }

    // Compare elements in two arrays
    for (int i = 0; i < arr1.length; ++i) {
        for (int j = 0; i < arr2.length; ++j) {
            if (arr1[i] == arr2[j]) {
                ++cnt;
                break;
            }
        }
    }

    // cnt would equal to the length of arr1 or arr2
    // if one array is the subset of the other one
    return (cnt == arr1.length || cnt == arr2.length);
}
JohnL10000
  • 1
  • 1
  • 1
  • 5

3 Answers3

0

You may need another array c to collect all the unique values of array b then compare the array a and array c.

Firok
  • 269
  • 1
  • 6
0

You can implement a custom containsAll method for two lists instead of arrays:

/**
 * @param a   first list.
 * @param b   second list.
 * @param <T> type of list elements.
 * @return whether the first list contains all the elements from the second list.
 */
public static <T> boolean containsAll(List<T> a, List<T> b) {
    // incorrect incoming data
    if (a == null || b == null) return false;
    // copy of the first list
    List<T> c = new ArrayList<>(a);
    // iterate through the second list and remove its
    // elements from the copy of the first list, if any
    for (T e : b) c.remove(e);
    // return whether the size of the first list
    // is equal to the size of the second list plus
    // what is left in the copy of the first list
    return a.size() == b.size() + c.size();
}

public static void main(String[] args) {
    List<Integer> a = Arrays.asList(1, 2, 3);
    List<Integer> b = Arrays.asList(1, 1);
    boolean isSubset = containsAll(a, b);
    System.out.println(isSubset); // false
}

See also: What is the quickest way to determine if two elements are in the same row or column in a 2D array?

0

You can implement a custom generic containsAll method for two arrays as follows:

/**
 * @param a   first array.
 * @param b   second array.
 * @param <T> type of array elements.
 * @return whether the first array contains
 * all the elements from the second array.
 */
public static <T> boolean containsAll(T[] a, T[] b) {
    // incorrect incoming data
    if (a == null || b == null) return false;
    // copy of the first array
    T[] c = Arrays.copyOf(a, a.length);
    // iterate through the second array and remove its
    // elements from the copy of the first array, if any
    for (T e : b)
        // iterate through the copy of the first array
        for (int i = 0; i < c.length; i++)
            // this element is equal to the
            // element from the second array
            if (c[i] != null && c[i].equals(e)) {
                // shift the subsequent elements back
                System.arraycopy(c, i + 1, c, i, c.length - i - 1);
                // truncate the array by one element
                c = Arrays.copyOf(c, c.length - 1);
                // exit the inner loop
                break;
            }
    // return whether the size of the first array
    // is equal to the size of the second array plus
    // what is left in the copy of the first array
    return a.length == b.length + c.length;
}

public static void main(String[] args) {
    Integer[] a = {1, 2, 3, 1};
    Integer[] b = {1, 1};
    boolean isSubset = containsAll(a, b);
    System.out.println(isSubset); // true
}