codeloopback
Guide contents

Lesson 71 of 164

Check if an Array Is a Subset of Another

Given two arrays a and b, return true if every element of b also appears in a, meaning b is a subset of a.

Example 1

Text
a = [9, 4, 7, 1, -2, 6, 5], b = [7, 1, -2]
Output: true

Example 2

Text
a = [9, 4, 7, 1, -2, 6, 5], b = [10, 12]
Output: false   (10 is not in a)

Brute force: search a for each element of b

Java
public class Main {
    static boolean contains(int[] a, int x) {
        for (int y : a) {
            if (y == x) return true;
        }
        return false;
    }

    static boolean isSubset(int[] a, int[] b) {
        for (int x : b) {
            if (!contains(a, x)) return false; // stops at the first missing element
        }
        return true;
    }

    public static void main(String[] args) {
        int[] a = {9, 4, 7, 1, -2, 6, 5};
        System.out.println(isSubset(a, new int[]{7, 1, -2}) + " " + isSubset(a, new int[]{10, 12}));
    }
}
Output
true false

Time: O(n·m), where n = a.length and m = b.length. Each contains call is a linear scan of a. Java has no contains method on int[], so the helper does the scan. Space: O(1).

The loop returns at the first element that is missing, so a false answer can come back early.

Java
import java.util.Arrays;

public class Main {
    static boolean isSubset(int[] a, int[] b) {
        int[] sorted = a.clone();
        Arrays.sort(sorted);
        for (int x : b) {
            if (Arrays.binarySearch(sorted, x) < 0) return false; // a negative result means "not found"
        }
        return true;
    }

    public static void main(String[] args) {
        int[] a = {9, 4, 7, 1, -2, 6, 5};
        System.out.println(isSubset(a, new int[]{7, 1, -2}) + " " + isSubset(a, new int[]{10, 12}));
    }
}
Output
true false

Time: O(n log n + m log n). Space: O(n) for the sorted copy. Arrays.binarySearch needs a sorted array and returns a negative number when the value is absent. Sort a in place instead of copying when memory is tight and changing the input is allowed.

Optimal: put a in a HashSet

Build a set from a once (O(n)), and each membership check becomes O(1) on average. A HashSet<Integer> stores boxed Integer objects, so each int is wrapped automatically on add and contains.

Walkthrough with b = [7, 1, -2]. The set is {9, 4, 7, 1, -2, 6, 5}:

element of b in set?
7 yes
1 yes
-2 yes → return true
Java
import java.util.HashSet;
import java.util.Set;

public class Main {
    static boolean isSubset(int[] a, int[] b) {
        Set<Integer> set = new HashSet<>();
        for (int x : a) set.add(x);
        for (int x : b) {
            if (!set.contains(x)) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] a = {9, 4, 7, 1, -2, 6, 5};
        System.out.println(isSubset(a, new int[]{7, 1, -2}) + " " + isSubset(a, new int[]{10, 12}));
        System.out.println(isSubset(a, new int[]{}));
    }
}
Output
true false
true

Time: O(n + m). Space: O(n) for the set.

Variant: duplicates must be matched

If b = [7, 7] should only count as a subset when a contains two 7s (a multiset subset), count the elements of a and use up one count per element of b. merge(x, 1, Integer::sum) adds 1 to the count of x, or stores 1 when x is absent. getOrDefault(x, 0) reads a count, or 0 when x is absent.

Java
import java.util.HashMap;
import java.util.Map;

public class Main {
    static boolean isSubMultiset(int[] a, int[] b) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int x : a) {
            counts.merge(x, 1, Integer::sum);
        }
        for (int x : b) {
            int left = counts.getOrDefault(x, 0);
            if (left == 0) return false;
            counts.put(x, left - 1);
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isSubMultiset(new int[]{7, 1, 7}, new int[]{7, 7}) + " " + isSubMultiset(new int[]{7, 1}, new int[]{7, 7}));
    }
}
Output
true false

Edge cases

  • Empty b: always a subset. The loop over b does not run, so the result is true.
  • Empty a with a non-empty b: false.
  • Duplicates in b: ignored by the set version, and matched one for one by the multiset variant.