Find whether an array is a subset of another array

Problem Statement

Given two arrays arr1[] and arr2[], determine whether arr2[] is a subset of arr1[]. Both arrays can contain duplicates. arr2[] is a subset of arr1[] if every element of arr2[] appears in arr1[] at least as many times.

Example:

• Input: arr1 = [11, 1, 13, 21, 3, 7], arr2 = [11, 3, 7, 1]
• Output: true
• Explanation: All elements of arr2 are present in arr1.

Approach 1: Brute Force (Nested Loops)

Intuition

For each element in arr2, search for it in arr1. Mark elements in arr1 as visited to handle duplicates.

Algorithm

1. For each element in arr2
2. Search for it in arr1
3. If found, mark it as visited (or track indices)
4. If any element is not found, return false

public class Solution {
    public boolean isSubset(int[] arr1, int[] arr2) {
        int m = arr1.length;
        int n = arr2.length;
        
        if (n > m) return false;
        
        boolean[] visited = new boolean[m];
        
        for (int i = 0; i < n; i++) {
            boolean found = false;
            for (int j = 0; j < m; j++) {
                if (!visited[j] && arr1[j] == arr2[i]) {
                    visited[j] = true;
                    found = true;
                    break;
                }
            }
            if (!found) return false;
        }
        
        return true;
    }
}

Complexity Analysis

• Time Complexity: O(m × n) - For each element in arr2, we may search entire arr1
• Space Complexity: O(m) - Visited array to handle duplicates

Approach 2: Sorting and Two Pointers

Intuition

Sort both arrays. Use two pointers to check if all elements of arr2 exist in arr1.

Algorithm

1. Sort both arrays
2. Use two pointers i (for arr1) and j (for arr2)
3. If arr1[i] == arr2[j], move both pointers
4. If arr1[i] < arr2[j], move i
5. If arr1[i] > arr2[j], element not found, return false

import java.util.Arrays;

public class Solution {
    public boolean isSubset(int[] arr1, int[] arr2) {
        int m = arr1.length;
        int n = arr2.length;
        
        if (n > m) return false;
        
        arr1 = arr1.clone();
        arr2 = arr2.clone();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        
        int i = 0, j = 0;
        
        while (i < m && j < n) {
            if (arr1[i] == arr2[j]) {
                i++;
                j++;
            } else if (arr1[i] < arr2[j]) {
                i++;
            } else {
                return false;  // arr2[j] not found in arr1
            }
        }
        
        return j == n;  // All elements of arr2 found
    }
}

Complexity Analysis

• Time Complexity: O(m log m + n log n) - Sorting both arrays
• Space Complexity: O(1) or O(m + n) - Depending on sorting algorithm

Approach 3: Optimal - Hashing with Frequency Count

Intuition

Use a hash map to count frequencies of elements in arr1. Then check if arr2 elements have sufficient frequency.

Algorithm

1. Build frequency map from arr1
2. For each element in arr2, check if it exists with count > 0
3. Decrement count after each match
4. Return false if any element not found

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public boolean isSubset(int[] arr1, int[] arr2) {
        if (arr2.length > arr1.length) return false;
        
        // Build frequency map from arr1
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr1) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        // Check if arr2 is a subset
        for (int num : arr2) {
            int count = freq.getOrDefault(num, 0);
            if (count == 0) {
                return false;
            }
            freq.put(num, count - 1);
        }
        
        return true;
    }
}

Complexity Analysis

• Time Complexity: O(m + n) - Build map in O(m), check arr2 in O(n)
• Space Complexity: O(m) - Hash map stores frequencies from arr1

Key Takeaways

1. Handle duplicates carefully - Frequency counting is essential when duplicates exist
2. Sorting enables two pointers - Sorted arrays allow efficient O(m + n) checking
3. Hashing is most efficient - O(m + n) time with simple implementation
4. Edge case: size check - arr2 cannot be subset if larger than arr1