350. Intersection of Two Arrays II

Array Hash Table Two Pointers Binary Search Sorting

Time: O(m+n)

Space: O(min(m,n)

Intuition

Count frequencies in the smaller array via a HashMap. Iterate the larger array: for each element, if it exists in the map with count > 0, add it to results and decrement the count.

Algorithm

1Build count map from nums1.
2For each val in nums2: if count[val] > 0, add to result, decrement count[val].
3Return result.

Example Walkthrough

Input: nums1 = [1,2,2,1], nums2 = [2,2]

1.count={1:2, 2:2}. Process 2: count[2]=1, result=[2]. Process 2: count[2]=0, result=[2,2].

Output: [2,2]

Common Pitfalls

•Unlike problem 349 (unique intersection), here duplicates matter - use counts, not a set.

350.cs

// Approach: Frequency HashMap on the first array; for each element in the
// second array consume a match if available, building the intersection.
// Time: O(m+n) Space: O(min(m,n))

public class Solution
{
    public int[] Intersect(int[] nums1, int[] nums2)
    {
        List<int> result = new List<int>();
        Dictionary<int, int> map = new Dictionary<int, int>();
        for (int i = 0; i < nums1.Length; i++)
        {
            if (!map.ContainsKey(nums1[i]))
                map.Add(nums1[i], 1);
            else
                map[nums1[i]] += 1;
        }
        for (int i = 0; i < nums2.Length; i++)
        {
            if (map.ContainsKey(nums2[i]) && map[nums2[i]] > 0)
            {
                result.Add(nums2[i]);
                map[nums2[i]] -= 1;
            }
        }

        return result.ToArray();
    }
}

Was this solution helpful?