Intersection of Two Arrays II
Easy · Arrays & Hashing · Array · Hash Table · Counting · Two Pointers · Sorting
Problem
You are given two integer arrays nums1 and nums2.
Return their multiset intersection: every value appears in the result as many times as it appears in both arrays, which is the smaller of its two counts. The result may be in any order.
Examples
Input: nums1 = [3,1,3,8,3], nums2 = [3,3,8] Output: [3,3,8]
3 appears three times and twice, so it is kept twice; 8 is kept once.
Input: nums1 = [1,2], nums2 = [3,4] Output: []
No value appears in both arrays.
Input: nums1 = [9,9], nums2 = [9,4,9,9] Output: [9,9]
9 appears twice in nums1, so only two copies are shared.
Constraints
- 1 <= len(nums1), len(nums2) <= 1000
- 0 <= nums1[i], nums2[i] <= 1000
Approaches
- Baseline: find an unused partner for each value — time O(n · m), space O(m)
Follow-up
If both arrays arrive sorted, walk them with two pointers and no map: O(1) extra space. If nums1 is much smaller, count nums1 and stream nums2. If nums2 lives on disk and does not fit in memory, read it in chunks against the counts of the small array, or sort both externally and merge.
Related problems
Start free on Cariara · Coding problems · System design studio
