Given two arrays: a1[0..n-1] of size n and a2[0..m-1] of size m, the task is to check whether a2[] is a subset of a1[] or not. Both arrays can be sorted or unsorted.
Input: a1 = [11, 1, 13, 21, 3, 7], a2 = [11, 3, 7, 1]
Output: "Yes"
Explanation: All elements of a2 are present in a1.
Input: a1 = [1, 2, 3, 4, 5, 6], a2 = [1, 2, 4]
Output: "Yes"
Explanation: All elements of a2 are present in a1.
Input: a1 = [10, 5, 2, 23, 19], a2 = [19, 5, 3]
Output: "No"
Explanation: Element 3 from a2 is not present in a1.
We need to verify that every element in a2 appears in a1 with at least the same frequency. The key insight is to count occurrences in a1 and then validate each element in a2 against these counts.
1000001 (since values ≤ 106) with zeros.a1 and increment the count for each element in the frequency array.a2:
"No" and exit immediately.a2 are processed successfully, output "Yes".void isSubset(vector& a1, vector& a2) {
vector freq(1000001, 0);
for (int x : a1) freq[x]++;
for (int x : a2) {
if (freq[x] == 0) {
cout << "No" << endl;
return;
}
freq[x]--;
}
cout << "Yes" << endl;
} public void isSubset(int[] a1, int[] a2) {
int[] freq = new int[1000001];
for (int x : a1) {
freq[x]++;
}
for (int x : a2) {
if (freq[x] == 0) {
System.out.println("No");
return;
}
freq[x]--;
}
System.out.println("Yes");
}def is_subset(self, a1, a2):
freq = [0] * 1000001
for x in a1:
freq[x] += 1
for x in a2:
if freq[x] == 0:
print("No")
return
freq[x] -= 1
print("Yes")isSubset(a1, a2) {
let freq = new Array(1000001).fill(0);
for (let x of a1) {
freq[x]++;
}
for (let x of a2) {
if (freq[x] === 0) {
console.log("No");
return;
}
freq[x]--;
}
console.log("Yes");
}Time Complexity: O(n + m), where n and m are the sizes of a1 and a2, as we traverse each array once.
Space Complexity: O(1) because we use a fixed-size array of 1000001 elements, independent of input size.
Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.