Check if an Array is a Subset of Another Array

Title: Check if an Array is a Subset of Another Array

In this guide, you’ll learn how to check whether one array is a subset of another in Java. An array arr2 is a subset of arr1 when every element of arr2 appears in arr1 at least as many times as it appears in arr2. That last part about counting occurrences is the detail that trips up most learners.

This is a common interview question because the naive solution looks correct until duplicates enter the picture. We’ll build a solution using a frequency map, trace it step by step, and then look at the mistakes that cause this exact problem to fail silently in practice.

Understanding the Problem

Given two integer arrays, arr1 (the superset candidate) and arr2 (the subset candidate), you need to determine if every value in arr2 is present in arr1, with enough copies to cover its occurrences in arr2.

For example, if arr1 = [1, 2, 2, 3] and arr2 = [2, 2], the answer is true because arr1 has two 2s. But if arr2 = [2, 2, 2], the answer becomes false because arr1 only has two 2s to offer, not three.

Approach / Algorithm Steps

1. Create a HashMap<Integer, Integer> to store how many times each value occurs in arr1.
2. Iterate over arr1 and populate the frequency map using getOrDefault to increment counts.
3. Iterate over arr2. For each value, look up its count in the frequency map.
4. If the count is zero or the value is missing from the map, return false immediately; arr2 cannot be a subset.
5. Otherwise, decrement the stored count for that value by one, since it has now been “used up” by this element of arr2.
6. If the loop over arr2 finishes without returning false, every element had enough remaining copies, so return true.

Java Program

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

public class SubsetChecker {

    public static boolean isSubset(int[] superset, int[] subset) {
        Map<Integer, Integer> frequency = new HashMap<>();

        for (int value : superset) {
            frequency.put(value, frequency.getOrDefault(value, 0) + 1);
        }

        for (int value : subset) {
            int count = frequency.getOrDefault(value, 0);
            if (count == 0) {
                return false;
            }
            frequency.put(value, count - 1);
        }

        return true;
    }

    public static void main(String[] args) {
        int[] arr1 = {11, 7, 1, 13, 21, 3, 7, 3};
        int[] arr2 = {11, 3, 7, 1};

        boolean result = isSubset(arr1, arr2);
        System.out.println("arr2 is a subset of arr1: " + result);
    }
}

Explanation of the Program

• The isSubset method takes the candidate superset and candidate subset as parameters and returns a boolean.
• The first loop builds a tally of every value in superset using a HashMap<Integer, Integer>, so lookups later are O(1) instead of scanning the array again.
• The second loop walks subset once. For each value, it reads the remaining count from frequency.
• A count of zero means every copy of that value has already been claimed by an earlier element of subset, or the value never existed in superset at all, so the method returns false right away.
• Decrementing the count after a successful match is what makes this solution correct for duplicates. Without it, the same value in superset could satisfy multiple requests from subset for free.
• If the loop finishes, main prints the result; for the sample data, every element of arr2 is accounted for in arr1, so the program prints true.

Step-by-Step Trace

Let’s trace isSubset on superset = [5, 1, 5, 2, 8] and subset = [5, 5, 1], which should return true. After the first loop, the frequency map holds {5: 2, 1: 1, 2: 1, 8: 1}. The table below follows the second loop, which checks each element of subset.

At the end of each iteration, frequency holds exactly how many more occurrences of that value are still available to satisfy later elements of subset. Since no iteration hit a count of zero before decrementing, the method returns true.

Examples

Example 1: A Valid Subset With Repeated Elements

This is the case the main program demonstrates: arr1 contains two 7s and two 3s, which is enough to cover the single 7 and single 3 requested by arr2.

int[] arr1 = {11, 7, 1, 13, 21, 3, 7, 3};
int[] arr2 = {11, 3, 7, 1};
// isSubset(arr1, arr2) returns true

Example 2: A Missing Element

Here, the value 6 never appears in arr1 at all, so the check fails on the very first lookup for it.

int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {2, 6};
// isSubset(arr1, arr2) returns false

Example 3: Present but Not Enough Copies

This example is why counting matters. The value 2 does exist in arr1, but only twice, while arr2 asks for three copies.

int[] arr1 = {1, 2, 2, 3};
int[] arr2 = {2, 2, 2};
// isSubset(arr1, arr2) returns false

Common Mistakes to Avoid

These are the mistakes learners most often make when solving this exact problem.

• Using a HashSet instead of a frequency map – checking membership with Set.contains() ignores how many times a value actually occurs, so arr2 = [2, 2, 2] against arr1 = [1, 2, 3] wrongly returns true. Use a HashMap<Integer, Integer> and decrement counts on each match instead.
• Nested loops without an early exit – comparing every element of subset against every element of superset with two for loops and no break wastes comparisons even after a match is found, turning an O(n + m) problem into O(n * m). Break out of the inner loop as soon as a match is found, or switch to the map-based approach entirely.
• Sorting the original arrays in place – calling Arrays.sort(arr1) directly on the caller’s array reorders it permanently, which silently breaks any code afterward that depends on the original order. Clone the array first with arr1.clone() before sorting if you need a sort-based approach.
• Treating an empty subset as a special case – adding an explicit check for subset.length == 0 before the main loop is unnecessary; the loop over an empty array simply never executes and correctly falls through to return true. Let the loop handle it naturally instead of adding a redundant branch.

Edge Cases to Test

A thorough answer walks through these boundary inputs without being asked.

• Empty subset array
• Empty superset array
• Subset larger than superset
• Duplicate values in subset exceeding their count in superset
• Identical arrays
• Single-element arrays
• Negative numbers present
• Integer.MIN_VALUE / Integer.MAX_VALUE present

Additional Considerations

The frequency-map approach runs in O(n + m) time, where n is the length of superset and m is the length of subset, since building the map and checking the subset are each a single pass. It uses O(n) extra space for the map in the worst case, when every element of superset is distinct.

A sort-based alternative runs in O(n log n + m log m) time with O(1) extra space (besides the sort itself), using two pointers after sorting. It trades the map’s memory cost for a slower, but allocation-light, comparison pass, and is worth mentioning if an interviewer asks for a constant-space variant.

A brute-force nested loop needs no extra space at all but costs O(n * m) time, which becomes impractical once either array grows past a few thousand elements. It’s an acceptable starting point in an interview, but you should be ready to explain why the frequency map is the better production choice.

The Integer.MIN_VALUE and Integer.MAX_VALUE edge case matters here because HashMap handles them as ordinary keys with no special treatment, but a sort-based or arithmetic-difference approach could overflow if you’re not careful about how boundary values are compared.

Interview Follow-up Questions

Once you’ve solved the base problem, expect an interviewer to push further with questions like these.

• What if both arrays are already sorted? – use a two-pointer scan over both arrays instead of a map; you only need O(1) extra space because the sorted order lets you advance each pointer in lockstep.
• What if you must solve this with O(1) extra space? – sort clones of both arrays in place and walk them with two pointers, since sorting avoids the map’s memory cost at the price of O(n log n) time.
• What if the elements are custom objects instead of integers? – the same HashMap approach works as long as the object’s class correctly overrides equals() and hashCode(), otherwise frequency lookups will silently miss matches.
• What if superset is a massive stream that doesn’t fit in memory? – build the frequency map incrementally as the stream is read, keeping memory proportional to the number of distinct values rather than the total number of elements, then validate subset once the stream ends.

Conclusion

Checking whether one array is a subset of another comes down to counting, not just membership. The frequency-map solution covers duplicates correctly in a single pass over each array, and the sort-based two-pointer variant is a solid fallback when extra memory isn’t an option.

Try adapting isSubset to work with Integer[] arrays or a custom type to see how the same pattern generalizes. You can learn more about arrays here: Arrays.