309. Intersection of Two Arrays II
Easy
Frequency Intersection
Hashing
Problem
Given two integer arrays nums1 and nums2, return their intersection while preserving multiplicity. Each element in the result must appear as many times as it occurs in both arrays. The result may be returned in any order.
Examples
Example 1
Input: [1,2,2,1], [2,2]
Output: [2,2]
Example 2
Input: [4,9,5], [9,4,9,8,4]
Output: [4,9]
Example 3
Input: [1], [2]
Output: []
Constraints
� 1 <= nums1.length, nums2.length <= 1000
� -1000 <= nums1[i], nums2[i] <= 1000
Hints
?? Count occurrences in one of the arrays.
?? When a value from the other array has a positive remaining count, add it to the answer and decrement the count.
Expected Complexity
Time: O(n + m)
Space: O(min(n, m))
Follow-up
What approach would you use if both arrays were sorted, or if one array were much smaller than the other?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[1,2,2,1], [2,2]Expected
[2,2]