Array Subset

?? Problem:

You're given two arrays: a1[] and a2[], where both may contain duplicates, and the goal is to determine whether a2[] is a subset of a1[]. The catch? The arrays are large, and the elements are of type long.

?? Approach:

Efficiently solve this problem using a frequency map to count occurrences in a1[] and validate against a2[].

Code Implementation

import java.Util.HashMap;

class Compute {
public String isSubset(long[] a1, long[] a2, long n, long m)
{
// Create a frequency map for a1[]
HashMap<Long, Integer> freqMap = new HashMap<>();

for(long num : a1)
{
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}

// Check elements of a2[] in the frequency map
for(long num : a2)
{
if(!freqMap.containsKey(num) ||  freqMap.get(num == 0)
{
return "No";   // Element not found or count exhausted
}

freqMap.put(num, freqMap.get(num) - 1);  // Decrease the count
}
return "Yes";   // All Elements of a2[] are present in a1[]
}
}        

How It Works

1?? Frequency Map:

• Create a map to count occurrences of each element in a1[].

2?? Validation:

• Traverse a2[] and check if each element exists in the map with sufficient occurrences.

3?? Output:

• If all elements of a2[] are found in a1[] with valid counts, return "Yes"; otherwise, return "No".

Example

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[] since all its elements exist in a1[] with valid counts.

Efficiency

• Time Complexity: O(max(n,m))O(\max(n, m))O(max(n,m))
• Space Complexity: O(n)O(n)O(n)

?? Explore the beauty of maps and efficient validations!