Given two integer arrays arr1 and arr2, arr1 is a subset of arr2 if every value in arr1 appears at least once in arr2.
Return true if arr1 is a subset of arr2 and false otherwise.
Example 1
Input: arr1 = [8, 2, 8, -3, 5], arr2 = [5, 10, 2, -3, 7, 8, 2, 12]
Output: true
Explanation: arr2 contains 8, 2, -3, and 5. Its single 8 satisfies both occurrences in arr1.
Example 2
Input: arr1 = [4, 6], arr2 = [7, 4]
Output: false
Explanation: 4 appears in arr2, but 6 is missing.
Approach
The subset check depends on which values appear in arr2. A value can be anywhere in that array. If it appears several times in arr1, one copy in arr2 is enough for all of them.
Searching arr2 from the start for each value in arr1 can mean checking the same elements many times. A hash set keeps one copy of each value in arr2. The set uses the value being searched for to work out where to look, so it can usually tell quickly whether that value is present.
If a value from arr1 is missing from the set, it is also missing from arr2. That single missing value makes the answer false. If every value from arr1 is in the set, then every value appears in arr2 and the answer is true.
Algorithm
Return
trueimmediately ifarr1is empty.Create an empty hash set for the available values.
Insert every value from
arr2. Repeated values share a single entry.Check each value from
arr1against the set and returnfalseon the first missing value.Return
truewhen all required values have passed the membership check.
Dry Run
Check if Array is Subset of Another
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns whether every value in arr1 occurs in arr2. bool isSubset(const vector<int>& arr1, const vector<int>& arr2) { // An empty arr1 has no membership requirements. if (arr1.empty()) { return true; } unordered_set<int> available; // Store each distinct available value once. for (int value : arr2) { available.insert(value); } // Check each required value without removing matches from the set. for (int value : arr1) { // A missing entry proves that the required value is absent. if (available.find(value) == available.end()) { return false; } } return true; }};// Driver codeint main() { vector<int> arr1 = {8, 2, 8, -3, 5}; vector<int> arr2 = {5, 10, 2, -3, 7, 8, 2, 12}; // instance for class Solution Solution sol; cout << boolalpha << sol.isSubset(arr1, arr2) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(M + N) expected because the hash set supports expected amortized O(1) insertions and expected O(1) lookups.
Space Complexity: O(D) auxiliary space, where D is the number of distinct values in arr2.
Interview follow-up Questions
Yes. For example, arr1 = [4, 4, 4] is a subset of arr2 = [4] because the single available 4 satisfies all three requirements. A length comparison alone cannot determine the result.
Be the first to add a comment.