Watch 10 video solutions for Intersection of Two Arrays II, a easy level problem involving Array, Hash Table, Two Pointers. This walkthrough by Fisher Coder has 23,011 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |