297. Intersection of Two Arrays II
You are given two integer arrays, nums1 and nums2. Return their intersection with multiplicity: a value shows up in the answer once per matched pair across the two inputs — that is, the smaller of its two occurrence counts.
To make the answer unique, return it sorted in increasing order (equal values sit next to each other). If the arrays share nothing, return an empty list (printed as an empty line).
Follow-up worth thinking about: what changes if nums2 is enormous and stored on disk, so you can only stream it?
Example 1:
Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2, 2]
Explanation: 2 occurs twice in nums1 and twice in nums2, so it appears min(2, 2) = 2 times. 1 never occurs in nums2, so it is dropped.
Example 2:
Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
Output: [4, 9]
Explanation: 4 occurs once in nums1 (though twice in nums2) → min(1, 2) = 1 copy. Same for 9. Sorted ascending: [4, 9].
Constraints:
- 1 ≤ nums1.length, nums2.length ≤ 10⁴
- -10⁹ ≤ nums1[i], nums2[i] ≤ 10⁹
Hints:
The answer for each value is min(count in nums1, count in nums2). A hash map can hold one array's counts.
Count nums1 in a map, then stream nums2: whenever a value still has a positive remaining count, emit it and decrement — the decrement is what caps the multiplicity.
If both arrays were sorted, two pointers advancing past the smaller value would emit each match exactly min(count) times with no map at all — handy for the streaming follow-up.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Expected output: [2, 2]