AlgoInsight

DSA problem

Intersection of Two Arrays II

EasyHash TablesPattern: Frequency Counttop600AmazonGoogleFacebookMicrosoftApple

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.

Unlike the basic intersection problem where duplicates are collapsed, here multiplicity matters: if a value appears 2 times in nums1 and 3 times in nums2, it should appear exactly 2 times (the minimum) in the output.

Follow-up questions worth considering: What if the arrays are already sorted? How would you optimize the algorithm then? What if nums1's size is small compared to nums2's size? What if elements of nums2 are stored on disk and memory is limited so you cannot load all elements into memory at once?

Examples

Example 1
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Explanation: The value 2 appears twice in nums1 and twice in nums2, so it appears min(2, 2) = 2 times in the result.
Example 2
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: The value 4 appears once in nums1 and twice in nums2 (min = 1). The value 9 appears once in nums1 and twice in nums2 (min = 1). The order [9,4] is also accepted.
Example 3
Input: nums1 = [1,2], nums2 = [1,1]
Output: [1]
Explanation: The value 1 appears once in nums1 and twice in nums2, so it appears min(1, 2) = 1 time.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

hash-tablearraytwo-pointerssortingbinary-search

Browse all DSA problems