Coding Interview PatternsIntersection of Two Arrays II
EasyHash Maps
Intersection of Two Arrays II
Explanation & Solution
Description
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. You may return the result in any order.
Input:nums1 = [1, 2, 2, 1], nums2 = [2, 2]
0
1
1
2
2
2
3
1
0
2
1
2
Output:[2, 2]
0
2
1
2
Explanation: The element 2 appears twice in both arrays, so it appears twice in the result.
Constraints
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
Approach
Hash Maps pattern
1. Build a Frequency Map for nums1
- Create a hash map
countMapto store the frequency of each element innums1 - Iterate through
nums1and increment the count for each number
2. Find Intersections Using nums2
- Iterate through each element in
nums2 - For each element, check if it exists in
countMapwith a count greater than 0 - If it does, add it to the
resultarray and decrement its count in the map - Decrementing ensures each element is used at most as many times as it appears in both arrays
3. Return the Result
- The
resultarray now contains all intersecting elements with the correct multiplicity - The order depends on the traversal of
nums2, but any order is accepted
Key Insight
- By counting elements in one array and then consuming counts while iterating the other, we naturally handle duplicates — each match reduces the available count by 1
Time
O(m + n) where m and n are the lengths of the two arraysSpace
**O(min(m, n))** — we can optimize by building the map from the smaller arrayVisualization
Input:
[1, 2, 2, 1]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps