Find whether an array is a subset of another array

The problem, simply

You get a big array a (length m) and a small array b (length n). Is b a subset of a? That means every number in b can be matched to its own copy in a.

Repeats matter. If b has three 3s, then a needs at least three 3s.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each number in b, search a for a copy that is not used yet, and mark it used.

1. Make used, a true or false mark for each box of a.
2. For each x in b, walk a looking for an unused box equal to x. Mark it used. If none is found, return false.

class Solution {
    public boolean isSubset(int[] a, int[] b) {
        if (b.length > a.length) return false;
        boolean[] used = new boolean[a.length];
        for (int x : b) {
            boolean found = false;
            for (int i = 0; i < a.length; i++) {
                if (!used[i] && a[i] == x) {   // an unused copy of x
                    used[i] = true;
                    found = true;
                    break;
                }
            }
            if (!found) return false;
        }
        return true;
    }
}

How long it takes: for each of the n numbers in b we may walk all m boxes, O(m * n). Extra room: the marks, O(m).

Way 2: the clever way

Count first, then spend the counts.

1. Walk a once and count each number in a hash map.
2. Walk b. For each x, if its count is 0 (or it is missing), return false. Otherwise lower the count by 1.
3. If you reach the end of b, return true.

class Solution {
    public boolean isSubset(int[] a, int[] b) {
        if (b.length > a.length) return false;
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : a) count.merge(x, 1, Integer::sum);     // piles of stickers
        for (int x : b) {
            int c = count.getOrDefault(x, 0);
            if (c == 0) return false;                         // pile is empty
            count.put(x, c - 1);                              // take one
        }
        return true;
    }
}

How long it takes: one walk over a and one over b, O(m + n) on average. Extra room: the map holds at most m different numbers, O(m).

Watch out for

• If b is longer than a, the answer is false right away.
• Build the counts from the big array, not the small one. Counting b and checking a answers a different question.
• An empty b is a subset of anything, including an empty a.

What interviewers ask next

• Both arrays are sorted? Walk them with two fingers: if a[i] < b[j] move i, if equal move both, if a[i] > b[j] then b[j] is missing, return false. O(m + n) time and O(1) room.
• Not sorted and no extra room allowed? Sort both, then use the two fingers: O(m log m + n log n).
• Can the small array be built from the letters of a magazine (ransom note)? Same counting, with 26 letter counts instead of a map.
• Is b a subsequence of a (same order, gaps allowed)? Different problem: one finger on each, and move the b finger only on a match.

Remember this

Grown-up words: the piles are a frequency map (a hash map from value to count), and "each copy used once" means we are checking a multiset subset.