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.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Explanation: [9,4] is also accepted.
Constraints:
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
Follow up:
nums1's size is small compared to nums2's size? Which algorithm is better?nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?Problem Overview: You get two integer arrays and need to return their intersection. Each element should appear as many times as it shows in both arrays. If a value appears twice in both arrays, it must appear twice in the result. Order of the result does not matter.
Approach 1: Hash Map Frequency Count (Time: O(n + m), Space: O(min(n, m)))
This approach counts how many times each number appears in one array using a hash map. Iterate through nums1 and store frequencies using a dictionary or map. Then iterate through nums2. For every value, check if it exists in the map and whether its frequency is still greater than zero. If it is, add the value to the result and decrement the stored count. The key insight is that hash lookups run in constant time, so you efficiently track duplicates without nested loops.
This method works well for unsorted arrays and is usually the fastest in practice. The extra memory is proportional to the number of distinct elements stored in the map. This technique heavily relies on hash tables and is a common pattern in many array frequency problems.
Approach 2: Sorting and Two Pointers (Time: O(n log n + m log m), Space: O(1) extra)
Sort both arrays first. After sorting, use two pointers starting at index 0 of each array. Compare the current elements. If the values match, append the number to the result and move both pointers forward. If one value is smaller, move the pointer of the smaller value forward to catch up. Sorting groups equal elements together, which makes it easy to count duplicates during the pointer scan.
This approach avoids using additional memory beyond the output list. The main cost comes from sorting both arrays. After sorting, the pointer traversal runs in linear time O(n + m). This technique demonstrates how two pointers can simplify comparison problems once the data is ordered.
Recommended for interviews: The hash map frequency method is usually the expected answer because it achieves linear time O(n + m) without sorting. Interviewers want to see that you recognize the frequency-count pattern with a hash map. The sorting + two pointer solution is still valuable to discuss, especially when memory usage matters or when arrays are already sorted. Showing both approaches demonstrates strong problem-solving flexibility.
This approach involves using a hash map (or dictionary) to keep track of the frequencies of elements in one of the arrays, then iterating through the second array to identify common elements, decrementing the frequency count accordingly.
We use Python's collections.Counter to track element frequencies in nums1. Then, we iterate through nums2, checking if the current element exists in the counter with a non-zero count: if so, we add the element to the intersection result and decrease its count in the counter.
Time Complexity: O(n + m), where n and m are the lengths of nums1 and nums2. Space Complexity: O(min(n, m)) due to the counter.
Another efficient way is to first sort both arrays and then use two pointers to identify intersections. This approach harnesses the ordered nature post-sort to efficiently match elements by moving through both arrays simultaneously.
Both arrays are initially sorted, and two pointers i and j iterate from the start of nums1 and nums2 respectively, by comparing elements. If matching, we add to the result; else, movements depend on comparatives.
Time Complexity: O(n log n + m log m) due to sorting of nums1 and nums2. Space Complexity: O(1) extra space is used, aside from the outputs.
| Approach | Complexity |
|---|---|
| Using Hash Maps for Frequency Count | Time Complexity: O(n + m), where n and m are the lengths of |
| Using Sorting and Two Pointers | Time Complexity: O(n log n + m log m) due to sorting of |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Frequency Count | O(n + m) | O(min(n, m)) | Best general solution for unsorted arrays and optimal interview performance |
| Sorting + Two Pointers | O(n log n + m log m) | O(1) extra (excluding output) | Useful when arrays are already sorted or when minimizing extra memory |
LeetCode 350: Intersection of Two Arrays II - Interview Prep Ep 50 • Fisher Coder • 23,011 views views
Watch 9 more video solutions →Practice Intersection of Two Arrays II with our built-in code editor and test cases.
Practice on FleetCode