Code Implementation

from collections import Counter

class Solution:
    def intersect(self, nums1, nums2):
        counts = Counter(nums1)
        result = []
        for num in nums2:
            if counts[num] > 0:
                result.append(num)
                counts[num] -= 1
        return result
      

#include <vector>
#include <unordered_map>

class Solution {
public:
    std::vector<int> intersect(std::vector<int>& nums1, std::vector<int>& nums2) {
        std::unordered_map<int, int> counts;
        for (int num : nums1) {
            counts[num]++;
        }
        std::vector<int> result;
        for (int num : nums2) {
            if (counts[num] > 0) {
                result.push_back(num);
                counts[num]--;
            }
        }
        return result;
    }
};
      

import java.util.*;

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums1) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        List<Integer> result = new ArrayList<>();
        for (int num : nums2) {
            if (counts.getOrDefault(num, 0) > 0) {
                result.add(num);
                counts.put(num, counts.get(num) - 1);
            }
        }
        int[] resArr = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resArr[i] = result.get(i);
        }
        return resArr;
    }
}
      

var intersect = function(nums1, nums2) {
    const counts = {};
    for (let num of nums1) {
        counts[num] = (counts[num] || 0) + 1;
    }
    const result = [];
    for (let num of nums2) {
        if (counts[num] > 0) {
            result.push(num);
            counts[num]--;
        }
    }
    return result;
};
      

Problem Description

Given two integer arrays nums1 and nums2, return an array that represents their intersection. Each element in the result must appear as many times as it shows in both arrays. The order of the result can be in any order.

• If an element appears k times in both arrays, it should appear k times in the result.
• You must not reuse elements from either array more than they appear.
• There may be multiple valid answers, but any one of them is acceptable.

Example:
nums1 = [1,2,2,1], nums2 = [2,2] → Output: [2,2]

Thought Process

To solve this problem, the first idea that comes to mind is to compare every element in nums1 with every element in nums2 and add the common ones to the result, making sure not to reuse elements. However, this approach would be slow for large arrays because it checks every possible pair.

We can do better by using a data structure to quickly check if an element from nums2 exists in nums1 and how many times. A hash map (dictionary) is perfect for this, as it allows us to count how many times each number appears in nums1 and then, as we scan through nums2, we can efficiently check if that number is still available to "match."

This is a shift from brute-force checking all pairs to using a counting strategy that leverages fast lookups.

Solution Approach

• Step 1: Count the occurrences of each number in nums1 using a hash map (or dictionary).
• Step 2: Create an empty list (or array) to hold the intersection result.
• Step 3: Iterate through each number in nums2:
  • If the number exists in the hash map and its count is greater than zero, add it to the result and decrease its count in the map by one (to avoid reusing it).
  • If the number is not in the map or its count is zero, skip it.
• Step 4: After processing all elements in nums2, return the result list/array.

We use a hash map because it gives us constant-time (O(1)) lookups and updates for counts, making the solution efficient.

Example Walkthrough

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

1. Count elements in nums1:
   • 4: 1
   • 9: 1
   • 5: 1
2. Scan through nums2:
   • 9: exists in map with count 1 → add to result ([9]), decrement count to 0
   • 4: exists in map with count 1 → add to result ([9,4]), decrement count to 0
   • 9: count now 0 → skip
   • 8: not in map → skip
   • 4: count now 0 → skip
3. Final result: [9, 4] (or [4, 9] — order doesn't matter)

Each step shows how we only include elements up to their minimum frequency in both arrays, and never reuse more than allowed.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n * m), where n and m are the lengths of nums1 and nums2. This is because for each element in one array, we scan the other to find a match.
  • Space Complexity: O(min(n, m)), for storing the result.
• Optimized hash map approach:
  • Time Complexity: O(n + m). We scan nums1 once to build the map, and nums2 once to build the result.
  • Space Complexity: O(min(n, m)), for the hash map and the result array.

The optimized solution is much faster and scales well for large arrays.

Summary

By using a hash map to count occurrences in one array, we efficiently find the intersection with the other array, ensuring we only include each element as many times as it appears in both. This method avoids unnecessary repeated comparisons, making the solution both simple and efficient. The key insight is to leverage fast lookups with a counting structure, which is a common and powerful technique in array problems.