Intersection of Two Arrays II
Last Updated: March 29, 2026
Understanding the Problem
This problem asks us to find the common elements between two arrays, but with a twist: we need to respect frequencies. If the number 2 appears three times in nums1 and twice in nums2, it should appear twice in the result (the minimum of the two counts).
This is different from "Intersection of Two Arrays" (LeetCode #349), which only asks for unique common elements. Here, duplicates matter. The key question is: how do we efficiently track how many times each element appears in both arrays and output the overlap?
Key Constraints:
1 <= nums1.length, nums2.length <= 1000-- With n up to 1000, even O(n^2) would be fine (at most 1 million operations). But we should still aim for cleaner, more scalable solutions.0 <= nums1[i], nums2[i] <= 1000-- Element values are small non-negative integers. This means we could use a fixed-size counting array of size 1001 instead of a hash map.- Given these constraints, O(n) with a hash map is the cleanest approach, while O(n log n) with sorting answers the follow-up about pre-sorted arrays.
Approach 1: Brute Force
Intuition
The most straightforward approach: for each element in nums1, search through nums2 to find a match. When you find one, add it to the result and mark that element in nums2 as "used" so it doesn't get matched again.
Think of it like pairing socks. You pick up one sock from the first pile, search through the second pile for its match, and when you find one, you pull both out. You keep going until you've checked every sock in the first pile.
Algorithm
- Create a boolean array to track which indices in
nums2have already been matched. - For each element in
nums1, scan throughnums2. - If you find an unmatched element in
nums2that equals the current element fromnums1, add it to the result and mark that index as used. - Return the result.
Example Walkthrough
Input:
For each element in nums1, we search nums2 for a match. Element 1 at index 0 has no match. Element 2 at index 1 matches nums2[0], mark it used. Element 2 at index 2 matches nums2[1], mark it used. Element 1 at index 3 has no match.
Code
- Time Complexity: O(m * n). For each of the m elements in
nums1, we potentially scan all n elements innums2. - Space Complexity: O(n). The
usedboolean array tracks which indices innums2have been matched.
This approach works but is slow for large inputs. What if we counted the frequency of each element in one array, so that finding matches takes O(1) instead of O(n)?
Approach 2: Hash Map (Frequency Count)
Intuition
Instead of scanning nums2 repeatedly, count the frequency of every element in nums1 using a hash map. Then walk through nums2: for each element, check if it exists in the map with a positive count. If it does, add it to the result and decrement the count. The hash map acts as an inventory that we draw from as we scan the second array.
One practical tip: always build the map from the smaller array. It uses less memory and the lookup phase scans the larger array, which keeps space usage minimal.
The hash map stores the "budget" for each element from nums1. When we encounter the same element in nums2, we spend one unit of that budget. If the budget hits zero, we've already matched as many copies as nums1 had, so any additional copies in nums2 get skipped. This naturally produces the correct count: min(count in nums1, count in nums2) for each element.
Algorithm
- If
nums1is longer thannums2, swap them so we always build the map from the smaller array. - Count the frequency of each element in
nums1using a hash map. - Iterate through
nums2. For each element, if it exists in the map with count > 0, add it to the result and decrement the count. - Return the result.
Example Walkthrough
Code
- Time Complexity: O(m + n). One pass through
nums1to build the map (O(m)), one pass throughnums2to find matches (O(n)). Each hash map operation is O(1) on average. - Space Complexity: O(min(m, n)). The hash map stores at most min(m, n) distinct elements since we build it from the smaller array.
This approach is already optimal in time, but it uses extra space for the hash map. If the arrays are already sorted (or we're willing to sort them), two pointers can find matches without any extra storage.
Approach 3: Sorting + Two Pointers
Intuition
Sort both arrays, then use two pointers to walk through them in tandem. When both pointers point to the same value, that value is in the intersection. When they differ, advance the pointer at the smaller value, since the smaller value can't possibly match anything ahead in the other sorted array.
This is particularly useful when the arrays come pre-sorted (the first follow-up question). In that case, we skip the O(n log n) sorting step entirely and go straight to the O(n) two-pointer scan.
Algorithm
- Sort both
nums1andnums2. - Initialize two pointers,
iat the start ofnums1andjat the start ofnums2. - While both pointers are within bounds:
- If
nums1[i] == nums2[j], add the value to the result and advance both pointers. - If
nums1[i] < nums2[j], advancei. - If
nums1[i] > nums2[j], advancej. - Return the result.
Example Walkthrough
Code
- Time Complexity: O(m log m + n log n). Sorting both arrays dominates the two-pointer scan which is O(m + n). If both arrays are already sorted, this drops to O(m + n).
- Space Complexity: O(1) extra space (excluding output). If we sort in-place, the only extra space is the result array.