27. Check if an Array Is a Subset of Another Array

Given two arrays a1 and a2, determine whether every element of a2 (respecting how many times each value appears) can be matched to an element of a1. Print 'Yes' or 'No'.

Input: The first line contains n1 followed by a line with n1 space-separated integers (array a1). The next line contains n2 followed by a line with n2 space-separated integers (array a2). Output: Print 'Yes' if every element of a2, respecting duplicate counts, can be matched in a1; otherwise print 'No'.

1 <= n1, n2 <= 10^5

Without decrementing counts as you match, a value appearing once in a1 but needed TWICE in a2 would incorrectly pass - the decrement step is what makes this a genuine multiset-subset check, not just a plain existence check.

Check whether every element of one array (respecting how many times each value repeats) can be found within another, bigger array. Brute force: For every element of a2, scan through a1 directly to check if it exists (and hasn't already been 'used up' by an earlier match) - this costs O(n1 * n2) in the worst case, slow for large arrays. Optimised: Building a frequency map of a1 ONCE up front lets every check against a2's elements be an instant O(1) hash lookup (with a decrement to correctly account for quantity), rather than re-scanning a1 from scratch for every single element of a2.

Sort a1 once. Then for each element of a2, use binary search to check whether it exists in a1; because binary search alone can't track how many copies have been 'consumed' when a2 has duplicates, pair it with tracking how many times each value has already been claimed (e.g. binary-searching for the value's range and counting how many of that range remain available). Replacing a full linear scan with a binary search for every element of a2 cuts the per-element lookup cost from linear to logarithmic. Time: O((n1 + n2) log n1) Space: O(n1) for the sorted copy

Build a hash map counting how many times each value appears in a1 with a single pass. Then scan a2 once, and for each value, check that the map has a remaining positive count for it and decrement that count as it's used; if any value in a2 is missing or already exhausted, the answer is 'No', otherwise it's 'Yes'. Both passes are linear and hashing gives O(1) average lookups, so this avoids both the quadratic scanning of the brute force and the sorting/log-factor overhead of the binary search approach entirely. Time: O(n1 + n2) Space: O(n1)

For every element of a2, linearly scan a1 looking for a matching value that hasn't already been 'used' by an earlier element of a2 (marking matched positions so the same a1 element isn't reused twice), returning 'No' the moment some element of a2 has no available match left, and 'Yes' if every element of a2 finds one. This directly implements the multiset-subset definition, but the linear scan of a1 for every element of a2 makes it quadratic overall. Time: O(n1 * n2) Space: O(n1) for the used-marker array

1. Build a frequency count of every value in the bigger array (a1). 2. Walk through the smaller array (a2) one element at a time. 3. For each element, check if it exists in the frequency map with a remaining count greater than zero - if so, use up one occurrence (decrement); if not, the subset check fails immediately. 4. If every element of a2 is successfully matched this way, a2 is a valid subset - answer Yes.

Time: O(n1 + n2) - one pass to build the frequency map from a1, one pass to check against a2. Space: O(n1), for the frequency map of the first array's distinct values.

n1 = n2 = 1 (smallest arrays); a2 containing more copies of a value than a1 has (must print 'No'); and n1, n2 at the largest size 10^5 to confirm a hashmap approach is needed over a naive scan.

Be explicit about the QUANTITY-aware nature of this check (not just 'does the value exist', but 'does it exist with enough remaining count') - decrementing the frequency count as you match each element is exactly what correctly enforces this.