Array Subset Check: 4 Methods in C++, Java, Python

Array B is a subset of array A when every element of B appears in A. Four methods solve the check, with time complexities ranging from O(m x n) down to O(m+n).

The original article on this problem had the right structure (four methods, clear complexity labels) but was too short to cover the implementation details interviewers actually probe. This rewrite fills that gap: working code in C++, Java, and Python, edge-case analysis, and a table you can pull up during placement prep.

What “Subset” Means for Arrays

Two quick examples:

• arr1 = {1, 2, 3, 4, 5}, arr2 = {3, 4, 5} — arr2 is a subset of arr1.
• arr3 = {1, 2, 3, 4, 5}, arr4 = {1, 2, 9} — arr4 is not a subset of arr3 (9 is absent).

Three edge cases worth clarifying before writing any code:

• Empty arr2: always a subset. No elements to check means the condition holds vacuously.
• arr2 equals arr1: a set is always a subset of itself.
• Duplicates: arr2 = {2, 2} with arr1 = {1, 2, 3}. The two-loop and binary-search approaches would say arr2 is a subset (they find 2 in arr1 both times). The hashing approach with frequency counts would say no, because arr1 has 2 exactly once but arr2 needs it twice. When the problem says “elements” without qualification, most placement questions treat it as a set-membership check. When it says “all occurrences” or “multiset”, use hashing with counts.

If you’re unsure, use hashing with counts. It handles both interpretations at the same O(m+n) complexity.

See finding min and max in an array and sorting array subranges for related array-manipulation patterns from the same placement coding rounds.

Method 1: Two Loops

The brute-force approach: for each element of arr2, scan all of arr1. Return false immediately when any arr2 element is missing.

Algorithm

• Use an outer loop to traverse arr2 (n elements).
• For each arr2[i], run an inner loop over all arr1[j] (m elements) looking for a match.
• If the inner loop completes without finding arr2[i], return false.
• If the outer loop completes, all elements were found — return true.

C++ Code

#include <iostream>
using namespace std;

bool isSubset(int arr1[], int m, int arr2[], int n) {
    for (int i = 0; i < n; i++) {
        bool found = false;
        for (int j = 0; j < m; j++) {
            if (arr2[i] == arr1[j]) {
                found = true;
                break;
            }
        }
        if (!found)
            return false;
    }
    return true;
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {3, 4, 5};
    int m = 5, n = 3;
    cout << (isSubset(arr1, m, arr2, n) ? "Subset" : "Not a subset") << endl;
    return 0;
}

Time complexity: O(m x n). Space complexity: O(1). The same logic works in plain C without modification.

For small arrays (m and n both under 100), this is acceptable. For the larger input sizes typical of placement coding rounds, use one of the three methods below.

Method 2: Sorting and Binary Search

Sort arr1 once, then run a binary search for each element of arr2. The sort pays a one-time cost so every subsequent lookup is O(log m) rather than O(m).

Algorithm

• Sort arr1 using std::sort (C++) or an equivalent.
• For each element in arr2, run a binary search on the sorted arr1.
• If binary search returns false for any element, return false.
• If all elements are found, return true.

C++ Code

#include <iostream>
#include <algorithm>
using namespace std;

bool binarySearch(int arr[], int low, int high, int x) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x)   return true;
        if (arr[mid] < x)    low = mid + 1;
        else                 high = mid - 1;
    }
    return false;
}

bool isSubset(int arr1[], int m, int arr2[], int n) {
    sort(arr1, arr1 + m);
    for (int i = 0; i < n; i++) {
        if (!binarySearch(arr1, 0, m - 1, arr2[i]))
            return false;
    }
    return true;
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {3, 4, 5};
    int m = 5, n = 3;
    cout << (isSubset(arr1, m, arr2, n) ? "Subset" : "Not a subset") << endl;
    return 0;
}

Time complexity: O(m log m + n log m). C++‘s std::sort uses introsort internally, which is O(m log m) worst-case. Each binary search is O(log m), run n times. Space complexity: O(1).

Note: this method modifies arr1 in place. If you need to preserve the original order, copy arr1 before sorting.

Method 3: Sorting and Merge Scan

Sort both arrays, then walk through them with two pointers. The traversal mirrors the merge step of merge sort, but only checks for presence rather than building a combined array.

Algorithm

• Sort arr1 and arr2.
• Set two pointers i = 0 (for arr1) and j = 0 (for arr2).
• While i is within arr1 and j is within arr2:
  • If arr1[i] < arr2[j]: advance i (arr2[j] may appear later in arr1).
  • If arr1[i] == arr2[j]: advance both (matched this arr2 element).
  • If arr1[i] > arr2[j]: arr2[j] is not in arr1 — return false.
• If j has reached n, all arr2 elements were found. Return true.

C++ Code

#include <iostream>
#include <algorithm>
using namespace std;

bool isSubset(int arr1[], int m, int arr2[], int n) {
    sort(arr1, arr1 + m);
    sort(arr2, arr2 + n);
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (arr1[i] < arr2[j]) {
            i++;
        } else if (arr1[i] == arr2[j]) {
            i++;
            j++;
        } else {
            return false;
        }
    }
    return (j == n);
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {3, 4, 5};
    int m = 5, n = 3;
    cout << (isSubset(arr1, m, arr2, n) ? "Subset" : "Not a subset") << endl;
    return 0;
}

Time complexity: O(m log m + n log n). The merge scan itself runs in O(m+n); the sort steps dominate. Space complexity: O(1).

This method handles duplicates correctly for the multiset interpretation. If arr2 = {2, 2} and arr1 = {1, 2, 3}, the scan will match the first 2, then reach arr1[i] = 3 vs arr2[j] = 2 and return false.

Method 4: Hashing

Build a frequency map from arr1, then verify that arr2’s elements are present with sufficient count. This is the approach placement coding rounds reward with full marks.

Algorithm

• Traverse arr1 and insert each element into a hash map with its occurrence count.
• Traverse arr2. For each element:
  • If it exists in the map with count greater than zero: decrement its count (handles duplicates).
  • Otherwise: return false.
• If traversal completes, return true.

C++ Code

#include <iostream>
#include <unordered_map>
using namespace std;

bool isSubset(int arr1[], int m, int arr2[], int n) {
    unordered_map<int, int> freq;
    for (int i = 0; i < m; i++)
        freq[arr1[i]]++;
    for (int i = 0; i < n; i++) {
        if (freq.find(arr2[i]) == freq.end() || freq[arr2[i]] == 0)
            return false;
        freq[arr2[i]]--;
    }
    return true;
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5};
    int arr2[] = {3, 4, 5};
    int m = 5, n = 3;
    cout << (isSubset(arr1, m, arr2, n) ? "Subset" : "Not a subset") << endl;
    return 0;
}

Java Code

import java.util.HashMap;

public class SubsetCheck {
    public static boolean isSubset(int[] arr1, int[] arr2) {
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int x : arr1)
            freq.put(x, freq.getOrDefault(x, 0) + 1);
        for (int x : arr2) {
            if (!freq.containsKey(x) || freq.get(x) == 0)
                return false;
            freq.put(x, freq.get(x) - 1);
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = {3, 4, 5};
        System.out.println(isSubset(arr1, arr2) ? "Subset" : "Not a subset");
    }
}

Python Code

Python’s collections.Counter builds the frequency map in one line, making the logic straightforward:

from collections import Counter

def is_subset(arr1, arr2):
    freq = Counter(arr1)
    for x in arr2:
        if freq[x] <= 0:
            return False
        freq[x] -= 1
    return True

arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5]
print("Subset" if is_subset(arr1, arr2) else "Not a subset")

Time complexity: O(m+n). Space complexity: O(m) for the frequency map.

The decrement step (freq[arr2[i]]-- in C++, freq[x] -= 1 in Python) is what makes duplicate handling correct. Without it, arr2 = {2, 2} would incorrectly pass against arr1 = {1, 2, 3}.

Complexity Summary and Method Selection

Method	Time Complexity	Space	Handles Duplicates
Two loops	O(m x n)	O(1)	No
Sort + binary search	O(m log m + n log m)	O(1)	No
Sort + merge	O(m log m + n log n)	O(1)	Yes
Hashing	O(m+n)	O(m)	Yes

Choosing between them:

• Placement test, no constraints given: use hashing. It is optimal on time and handles duplicates. State that space is O(m); interviewers follow up on this.
• Memory constrained: sort + merge. Same correctness as hashing, O(1) space, at the cost of modifying both input arrays.
• arr1 is already sorted: skip the sort step in Method 2 or 3 and apply binary search directly. This reduces Method 2 to O(n log m).
• Quick prototype or test script: Python’s set(arr2).issubset(set(arr1)) is one line and correct for inputs with no duplicates.

For the data structures interview questions that appear in TCS NQT, Cognizant, and CoCuBES coding rounds, expect a follow-up on time complexity after submitting working code. The table above is what that follow-up tests.

The jump from O(m x n) to O(m+n) illustrates a principle that applies well beyond this problem: spending hash-table memory to buy faster lookups. That same trade-off shapes how production LLMs handle key-value caching during inference. TinkerLLM (₹299) runs a live model in your browser, no GPU or cloud account required, so you can see the principle at work in a real deployed system.