Intersection of Two Arrays II — Frequency Matching

LeetCode #350 Intersection of Two Arrays II is one of the first problems where brute force feels easy but the optimal solution teaches you a pattern you will use dozens of times. The problem asks you to return the intersection of two arrays, including duplicates — and that word "duplicates" is what makes frequency counting the right tool.

This is not just an array problem. It is the introduction to the Counter/decrement pattern that powers Ransom Note (#383), Valid Anagram (#242), Permutation in String (#567), and Minimum Window Substring (#76). Master the counting technique here and you have a template for all of them.

The two main approaches — hash map frequency counting and sort plus two pointers — each shine in different scenarios. Understanding when to pick which is exactly the kind of judgment interviewers look for.

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

The key distinction from Intersection of Two Arrays I (#349) is the "as many times as it shows in both" requirement. In problem #349, you return unique common elements. Here, if 2 appears twice in nums1 and three times in nums2, the result must include 2 exactly twice — the minimum frequency across both arrays.

This frequency-aware matching is what makes the problem interesting. A simple set intersection would lose the duplicate information, so you need a data structure that tracks counts, not just presence.

The hash map approach is the most intuitive. Build a frequency map from one array, then iterate through the other. For each element in the second array, if the count in the map is greater than zero, include the element in the result and decrement the count.

A smart optimization is to always count the smaller array. This minimizes the hash map size and keeps space usage at O(min(m, n)) instead of O(m) or O(n). The time complexity is O(m + n) regardless — you scan each array once.

The decrement step is what prevents over-counting. If nums1 has two 2s and nums2 has three 2s, the map starts with count 2 for the key 2. As you iterate nums2, you include 2 and decrement to 1, then include 2 again and decrement to 0. The third 2 in nums2 sees count 0 and gets skipped.

If the arrays are already sorted — or if you are told they will be in a follow-up — the two pointers approach avoids using a hash map entirely. Sort both arrays, then use one pointer for each. Compare the elements at both pointers.

If the elements are equal, include the value in the result and advance both pointers. If the element in nums1 is smaller, advance the nums1 pointer. If the element in nums2 is smaller, advance the nums2 pointer. This works because sorted order guarantees that advancing the smaller pointer is the only way to find a match.

The time complexity is O(n log n + m log m) due to sorting, with O(1) extra space if you do not count the output array. This approach is better when memory is constrained or when the input is already sorted.

Let us trace the hash map approach with nums1 = [1,2,2,1] and nums2 = [2,2]. First, build the frequency map from nums1 (the smaller array in practice, but either works here): {1: 2, 2: 2}.

Iterate nums2. Element 2: count is 2, so push 2 to result and decrement to 1. Element 2 again: count is 1, so push 2 to result and decrement to 0. Final result: [2, 2]. That matches the expected output.

Now try nums1 = [4,9,5] and nums2 = [9,4,9,8,4]. Map from nums1: {4: 1, 9: 1, 5: 1}. Iterate nums2: 9 has count 1, push and decrement. 4 has count 1, push and decrement. Second 9 has count 0, skip. 8 not in map, skip. Second 4 has count 0, skip. Result: [9, 4] which matches [4, 9] in any order.

When there is no intersection — for example nums1 = [1,2] and nums2 = [3,4] — the hash map approach naturally returns an empty array because no element in nums2 has a positive count in the map.

If one array is empty, the result is always empty. The hash map of an empty array has no entries, so nothing in the other array can match. Similarly, the two pointers approach exits immediately because one pointer is already past its array.

When all elements are the same — say nums1 = [3,3,3] and nums2 = [3,3] — the result is [3,3], limited by the smaller count. The frequency map records 3 with count 3, and the iteration decrements twice before the shorter array is exhausted.

Intersection of Two Arrays II is the gateway to frequency matching. The count-and-decrement pattern you learn here is the same one used in Ransom Note (#383) where you check if a magazine has enough letters, in Valid Anagram (#242) where you verify two strings have identical character frequencies, and in every sliding window problem that tracks character counts.

The follow-up questions in the problem description are worth studying. What if the arrays are already sorted? Use two pointers for O(1) space. What if nums1 is small and nums2 is very large and stored on disk? Sort nums1, then binary search each element of nums2 — no need to load the entire large array into memory.

Practice both approaches until you can write them from memory. The hash map version is your default for unsorted input. The two pointers version is your go-to when space matters or input is pre-sorted. YeetCode flashcards help you drill the frequency matching template so the pattern is automatic in your next interview.