Intersection of Two Arrays - Solution & Explanation
Problem Statement
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] Explanation: [4,9] is also accepted.
Constraints:
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
Approach Overview
Problem Overview: You receive two integer arrays and must return their intersection. The result should contain only unique values that appear in both arrays, and the order does not matter.
Approach 1: Using Hash Sets (O(m + n) time, O(m + n) space)
This is the most direct solution. Insert all elements of the first array into a hash set, then iterate through the second array and check whether each value exists in the set. If the lookup succeeds, add it to a result set to ensure uniqueness. Hash lookups run in average O(1) time, so the overall complexity becomes linear relative to the total number of elements. This approach works well for unsorted inputs and demonstrates practical use of a hash table to eliminate duplicates efficiently.
The key insight is that sets automatically handle uniqueness. Instead of manually checking whether a value was already added, the set structure guarantees that duplicates are ignored. In interviews, this approach is usually the first optimized solution candidates present because it is easy to reason about and scales well for large arrays.
Approach 2: Sorting and Two Pointers (O(m log m + n log n) time, O(1) extra space)
If modifying the arrays is allowed, sorting both arrays enables a pointer-based scan. First sort the arrays using any efficient sorting algorithm. Then place one pointer at the start of each array and move them forward depending on the comparison of the current values. When the numbers match, add the value to the result and advance both pointers while skipping duplicates.
This approach relies on the idea that once arrays are sorted, equal elements align naturally during a linear scan. The two pointers technique avoids nested loops and reduces comparison overhead. The total runtime is dominated by the sorting step, which is O(m log m + n log n). The scan itself runs in O(m + n). This technique is common in problems involving sorted arrays and belongs to the broader family of sorting-based optimizations.
Recommended for interviews: The hash set solution is typically expected because it achieves optimal O(m + n) time and is easy to implement in languages like Python, Java, or C++. The sorting + two pointers method is still valuable to discuss. It shows you understand alternative strategies and how pointer techniques reduce comparisons when working with ordered data.
Approach 1: Using Hash Sets
This approach utilizes hash sets to efficiently track and identify unique intersections between the two arrays. By converting one of the arrays into a set, we can check for existence of elements in constant time, and we store intersections in another set to ensure uniqueness.
This C solution uses a simple hash set implementation to find intersections. The set is represented by an array, and a naive hash function is used. It handles collisions with linear probing. Two sets are used: one for storing unique elements of nums1, and another for the results.
Complexity
Time complexity is O(n + m) for inserting and checking elements, with n and m being the sizes of nums1 and nums2 respectively. Space complexity is O(n + m) for the two sets used.
Approach 2: Using Sorting and Two Pointers
This approach sorts both arrays and uses two pointers to identify the intersection. The sorted order ensures that we can efficiently find common elements in a single pass through both arrays.
This C solution sorts both arrays and uses two pointers to traverse them. The pointers move forward when differences are found, and add elements to the result only if they are equal and haven't been added before, ensuring uniqueness.
Complexity
Time complexity is O(n log n + m log m) due to sorting, where n and m are the sizes of nums1 and nums2. Space complexity is O(n + m) for storing the sorted arrays.
Approach 3: Hash Table or Array
First, we use a hash table or an array s of length 1001 to record the elements that appear in the array nums1. Then, we iterate through each element in the array nums2. If an element x is in s, we add x to the answer and remove x from s.
After the iteration is finished, we return the answer array.
The time complexity is O(n+m), and the space complexity is O(n). Here, n and m are the lengths of the arrays nums1 and nums2, respectively.
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Hash Sets | Time complexity is O(n + m) for inserting and checking elements, with n and m being the sizes of nums1 and nums2 respectively. Space complexity is O(n + m) for the two sets used. |
| Using Sorting and Two Pointers | Time complexity is O(n log n + m log m) due to sorting, where n and m are the sizes of nums1 and nums2. Space complexity is O(n + m) for storing the sorted arrays. |
| Hash Table or Array | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set Lookup | O(m + n) | O(m + n) | General case for unsorted arrays; fastest average solution |
| Sorting + Two Pointers | O(m log m + n log n) | O(1) | When arrays can be sorted and memory usage must stay minimal |
| Sorting + Binary Search | O(m log n) | O(1) | When one array is sorted and repeated binary searches are acceptable |
Video Solution
Intersection of Two Arrays - Leetcode 349 - Python • NeetCodeIO • 33,444 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Intersection of Two Arrays easy or hard?
Intersection of Two Arrays Python/Java solution
How to solve Intersection of Two Arrays in O(n)?
What is the best approach for Intersection of Two Arrays?
Is Intersection of Two Arrays asked at Google/Amazon/Meta?
What data structure is used in Intersection of Two Arrays?
What is the time complexity of Intersection of Two Arrays?
Ready to solve this problem?
Practice Intersection of Two Arrays with our built-in code editor and test cases.
Practice on FleetCode