Intersection of Two Arrays II - Solution & Explanation
Problem Statement
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:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if
nums1's size is small compared tonums2's size? Which algorithm is better? - What if elements of
nums2are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
Approach Overview
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 1: Using Hash Maps for Frequency Count
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.
Complexity
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.
Approach 2: Using Sorting and Two Pointers
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.
Complexity
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 3: Hash Table
We can use a hash table cnt to count the occurrences of each element in the array nums1. Then, we iterate through the array nums2. If an element x is in cnt and the occurrence of x is greater than 0, we add x to the answer and then decrement the occurrence of x by one.
After the iteration is finished, we return the answer array.
The time complexity is O(m + n), and the space complexity is O(m). Here, m and n are the lengths of the arrays nums1 and nums2, respectively.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
Complexity Comparison
| 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 |
| Hash Table | — |
Detailed Complexity Analysis
| 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 |
Video Solution
LeetCode 350: Intersection of Two Arrays II - Interview Prep Ep 50 • Fisher Coder • 23,027 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Intersection of Two Arrays II easy or hard?
Intersection of Two Arrays II Python/Java solution
How to solve Intersection of Two Arrays II in O(n)?
What is the best approach for Intersection of Two Arrays II?
Is Intersection of Two Arrays II asked at Google/Amazon/Meta?
What data structure is used in Intersection of Two Arrays II?
What is the time complexity of Intersection of Two Arrays II?
Ready to solve this problem?
Practice Intersection of Two Arrays II with our built-in code editor and test cases.
Practice on FleetCode