350. Intersection of Two Arrays II
easyReturn the intersection of two arrays, including duplicates as many times as both arrays contain them. Hash-map counts of the smaller array, decrement while scanning the larger — the canonical 'occurs in both at least k times' pattern.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
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.
Constraints
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
Examples
Example 1
nums1 = [1,2,2,1], nums2 = [2,2][2,2]Example 2
nums1 = [4,9,5], nums2 = [9,4,9,8,4][4,9]Explanation: [9,4] is also accepted.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
If a value appears 3 times in one array and 5 times in the other, it appears min(3, 5) = 3 times in the result.
Hint 2
Count one array's elements with a hash map; walk the other array, appending and decrementing when count > 0.
Hint 3
For memory efficiency, count the smaller array. Sorting both and merging is a clean alternative if you can't use extra memory.
Solution approach
Reveal approach
Counter on the smaller of the two arrays. Walk the larger array; for each num, if counter[num] > 0, append num to result and decrement counter[num]. Return result. The 'min of two counts per element' semantics emerges naturally — the counter saturates at the smaller array's count, and the scan stops adding once it's depleted. O(n + m) time, O(min(n, m)) extra space. If the inputs are already sorted, two-pointer merge avoids the hash map entirely: i, j start at 0; advance the smaller; on equal, append and advance both. O(n + m) time, O(1) extra space.
Complexity
- Time
- O(n + m)
- Space
- O(min(n, m))
Related patterns
- hash-table
- counting
- two-pointers
- sorting
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
Practice these live with InterviewChamp.AI
Drill Intersection of Two Arrays II and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →