Array Subset of another array

Problem

Given two arrays: a1[0..n-1] of size n and a2[0..m-1] of size m, where both arrays may contain duplicate elements. The task is to determine whether array a2 is a subset of array a1. It's important to note that both arrays can be sorted or unsorted. Additionally, each occurrence of a duplicate element within an array is considered as a separate element of the set.

Examples

Example 1:

Input:
a1[] = {11, 7, 1, 13, 21, 3, 7, 3}
a2[] = {11, 3, 7, 1, 7}
Output:
Yes
Explanation:
a2[] is a subset of a1[]

Example 2:

Input:
a1[] = {1, 2, 3, 4, 4, 5, 6}
a2[] = {1, 2, 4}
Output:
Yes
Explanation:
a2[] is a subset of a1[]

Example 3:

Input:
a1[] = {10, 5, 2, 23, 19}
a2[] = {19, 5, 3}
Output:
No
Explanation:
a2[] is not a subset of a1[]

Your Task:

You don't need to read input or print anything. Your task is to complete the function isSubset() which takes the array a1[], a2[], its size n and m as inputs and return "Yes" if arr2 is subset of arr1 else return "No" if arr2 is not subset of arr1.

• Expected Time Complexity: $O(max(n,m))$
• Expected Auxiliary Space: $O(n)$

Constraints:

• $1 <= n,m <= 10^5$
• $1 <= a1[i], a2[j] <= 10^6$

Solution

Python

def isSubset(a1, a2, n, m):
    count_a1 = {}
    count_a2 = {}
    for num in a1:
        count_a1[num] = count_a1.get(num, 0) + 1
    for num in a2:
        count_a2[num] = count_a2.get(num, 0) + 1
    for num in count_a2:
        if num not in count_a1 or count_a1[num] < count_a2[num]:
            return "No"
    return "Yes"

Java

public String isSubset( long a1[], long a2[], long n, long m) {
    Map<Long, Integer> count_a1 = new HashMap<>();
    Map<Long, Integer> count_a2 = new HashMap<>();
    for (long num : a1) {
        count_a1.put(num, count_a1.getOrDefault(num, 0) + 1);
    }
    for (long num : a2) {
        count_a2.put(num, count_a2.getOrDefault(num, 0) + 1);
    }
    for (long num : count_a2.keySet()) {
        if (!count_a1.containsKey(num) || count_a1.get(num) < count_a2.get(num)) {
            return "No";
        }
    }
    return "Yes";
}

C++

string isSubset(int a1[], int a2[], int n, int m) {
    unordered_map<int, int> count_a1;
    unordered_map<int, int> count_a2;
    for (int i = 0; i < n; ++i) {
        count_a1[a1[i]]++;
    }
    for (int i = 0; i < m; ++i) {
        count_a2[a2[i]]++;
    }
    for (const auto& pair : count_a2) {
        int num = pair.first;
        int count_in_a2 = pair.second;
        if (count_a1.find(num) == count_a1.end() || count_a1[num] < count_in_a2) {
            return "No";
        }
    }
    return "Yes";
}

C

char* isSubset(int a1[], int a2[], int n, int m) {
    int *count_a1 = (int *)calloc(1001, sizeof(int));
    int *count_a2 = (int *)calloc(1001, sizeof(int));
    for (int i = 0; i < n; ++i) {
        count_a1[a1[i]]++;
    }
    for (int i = 0; i < m; ++i) {
        count_a2[a2[i]]++;
    }
    for (int i = 0; i < 1001; ++i) {
        if (count_a2[i] > 0 && count_a1[i] < count_a2[i]) {
            free(count_a1);
            free(count_a2);
            return "No";
        }
    }
    free(count_a1);
    free(count_a2);
    return "Yes";
}

• Time Complexity: $O(n+m)$
• Auxiliary Space: $O(n+m)$