Log inSign up
easyLeetCodeNot Started

Intersection of Two Arrays

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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 · Standard Overlapping Arrays:

Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2]
Explanation: The common element between [1, 2, 2, 1] and [2, 2] is 2. Since result must contain unique elements, return [2].

Example 2 · Multiple Common Elements:

Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
Output: [9, 4]
Explanation: Both 9 and 4 are present in both arrays. [4, 9] is also an acceptable valid output.

Example 3 · Disjoint Arrays (No Intersection):

Input: nums1 = [1, 3, 5], nums2 = [2, 4, 6]
Output: []
Explanation: There are no shared elements between the two arrays, so the output is an empty array [].

Constraints:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Hash Set operations (insert, search, delete in O(1) average time)
  • Two Pointers technique on sorted arrays
  • Understanding uniqueness and set theory intersection

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the use of Hash Sets for O(1) lookup and automatic deduplication.
  • Implement the Two-Pointer intersection technique on sorted collections with duplicate skipping.
  • Analyze trade-offs between O(N + M) space-heavy hashing vs. O(N log N + M log M) in-place sorting.
  • Write clean, idiomatic solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem asks for common elements between two collections where output elements must be distinct/unique.
  • Input elements are unsorted by default, but values or sizes allow O(1) hashing or O(N log N) sorting.
  • Need fast existence checks for elements of one array inside another.

Algorithmic Decision Tree:

  • If unsorted and memory is available: insert nums1 into a Hash Set, iterate through nums2 for O(N + M) time and O(N) space.
  • If arrays are already sorted or memory is strictly O(1): use Two Pointers moving left-to-right while skipping duplicate values.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Brute Force — Nested Linear Search

Intuition

For each element in nums1, linearly scan nums2 to check if it exists. If found, add it to the result array only if not already added.

Algorithm

  1. Initialize an empty list result.
  2. For each number x in nums1:
  3. Scan nums2 to see if x exists in nums2.
  4. If x exists in nums2, check if x is already in result.
  5. If not in result, append x to result.
  6. Return result.

Nested Loops Deduplication (O(M*N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Element 1 does not match
Visual state
Values and pointers at this exact step
hashmap
Input array
S
1
2
0
↑ check
1
Hash map state
Execution state
result[]
1 != 2. No match.
Variables at this step
result
[]
Check / comparison
Compare nums1[0] (1) with nums2[0] (2)
Decision / next transition
1 != 2. No match.
Why this step matters

Element 1 does not match.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6// Brute Force: Linear search in nums2 and deduplication in result
7vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
8 vector<int> result;
9
10 for (int x : nums1) {
11 // Check if x exists in nums2
12 bool inNums2 = false;
13 for (int y : nums2) {
14 if (x == y) {
15 inNums2 = true;
16 break;
17 }
18 }
19
20 // If in nums2, check if already in result
21 if (inNums2) {
22 bool inResult = false;
23 for (int r : result) {
24 if (r == x) {
25 inResult = true;
26 break;
27 }
28 }
29 if (!inResult) {
30 result.push_back(x);
31 }
32 }
33 }
34
35 return result;
36}
37
38int main() {
39 vector<int> nums1 = {1, 2, 2, 1};
40 vector<int> nums2 = {2, 2};
41 vector<int> res = intersection(nums1, nums2);
42
43 cout << "Output: [";
44 for (size_t i = 0; i < res.size(); i++) {
45 cout << res[i] << (i + 1 < res.size() ? ", " : "");
46 }
47 cout << "]" << endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Approach 1: Brute Force — Nested Linear Search.
  • Space complexity: O(1) — Space complexity for Approach 1: Brute Force — Nested Linear Search.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Better — Sort Both Arrays + Two Pointers

Intuition

Sort both arrays in ascending order, then traverse them using two pointers while skipping duplicate values.

Algorithm

  1. Sort nums1 and nums2 in ascending order.
  2. Initialize i = 0, j = 0, and an empty list result.
  3. While i < nums1.length and j < nums2.length:
  4. If nums1[i] == nums2[j]:
  5. If result is empty OR result.back() != nums1[i], append nums1[i] to result.
  6. Increment both i++ and j++.
  7. Else if nums1[i] < nums2[j], increment i++.
  8. Else, increment j++.
  9. Return result.

Sort Both Arrays + Two Pointers (O(M log M + N log N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Smaller element cannot match; advance i
Visual state
Values and pointers at this exact step
hashmap
Input array
S
1
1
2
2
0
↑ i
1
2
3
Hash map state
Execution state
i0
j0
result[]
1 < 2. Advance pointer i to 1.
Variables at this step
i
0
j
0
result
[]
Check / comparison
Sorted nums1: [1, 1, 2, 2]. Sorted nums2: [2, 2]. Compare nums1[0] (1) with nums2[0] (2)
Decision / next transition
1 < 2. Advance pointer i to 1.
Why this step matters

Smaller element cannot match; advance i.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6// Two Pointers on sorted arrays
7vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
8 sort(nums1.begin(), nums1.end());
9 sort(nums2.begin(), nums2.end());
10
11 vector<int> result;
12 int i = 0, j = 0;
13 int n = nums1.size(), m = nums2.size();
14
15 while (i < n && j < m) {
16 if (nums1[i] == nums2[j]) {
17 // Avoid duplicate entries in result
18 if (result.empty() || result.back() != nums1[i]) {
19 result.push_back(nums1[i]);
20 }
21 i++;
22 j++;
23 } else if (nums1[i] < nums2[j]) {
24 i++;
25 } else {
26 j++;
27 }
28 }
29
30 return result;
31}
32
33int main() {
34 vector<int> nums1 = {4, 9, 5};
35 vector<int> nums2 = {9, 4, 9, 8, 4};
36 vector<int> res = intersection(nums1, nums2);
37
38 cout << "Output: [";
39 for (size_t k = 0; k < res.size(); k++) {
40 cout << res[k] << (k + 1 < res.size() ? ", " : "");
41 }
42 cout << "]" << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Approach 2: Better — Sort Both Arrays + Two Pointers.
  • Space complexity: O(N) — Space complexity for Approach 2: Better — Sort Both Arrays + Two Pointers.

3. Optimal — Hash Set Lookup (Linear Time)

Intuition

Store all elements of nums1 in a hash set, then iterate through nums2 to check for matches and collect unique elements.

Algorithm

  1. Create a hash set set1 containing all unique elements of nums1.
  2. Create a hash set resultSet to store unique intersection elements.
  3. For each number x in nums2:
  4. If x exists in set1, insert x into resultSet.
  5. Convert resultSet into an array/vector and return it.

Hash Set Lookup (O(M + N) Time, O(min(M, N)) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Set eliminates duplicates from nums1 automatically
Visual state
Values and pointers at this exact step
hashmap
Input array
S
1
2
0
↑ set1
1
Hash map state
2 stored entries
key
1
maps to index
present
key
2
maps to index
present
Lookup operations in set1 are now O(1) average time.
Variables at this step
map state
1: present, 2: present
result
[]
Check / comparison
Build hash set from nums1: set1 = { 1, 2 }
Decision / next transition
Lookup operations in set1 are now O(1) average time.
Why this step matters

Set eliminates duplicates from nums1 automatically.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_set>
3#include <vector>
4using namespace std;
5
6// Optimal: Hash Set lookup for O(N + M) time
7vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
8 // Store unique elements of nums1 in a hash set
9 unordered_set<int> set1(nums1.begin(), nums1.end());
10 unordered_set<int> resultSet;
11
12 // Check presence of each element in nums2
13 for (int x : nums2) {
14 if (set1.count(x)) {
15 resultSet.insert(x);
16 }
17 }
18
19 // Convert result set to vector
20 return vector<int>(resultSet.begin(), resultSet.end());
21}
22
23int main() {
24 vector<int> nums1 = {1, 2, 2, 1};
25 vector<int> nums2 = {2, 2};
26 vector<int> res = intersection(nums1, nums2);
27
28 cout << "Output: [";
29 for (size_t i = 0; i < res.size(); i++) {
30 cout << res[i] << (i + 1 < res.size() ? ", " : "");
31 }
32 cout << "]" << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Approach 3: Optimal — Hash Set Lookup (Linear Time).
  • Space complexity: O(1) — Space complexity for Approach 3: Optimal — Hash Set Lookup (Linear Time).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Nested Scans)O(N * M)O(min(N, M))No extra data structures, simple to code.Good as an initial baseline, but must be optimized immediately.
2.Sort + Two PointersO(N log N + M log M)O(1) auxiliaryO(1) extra memory (ignoring sort stack), naturally handles deduplication.Excellent follow-up when interviewer asks: 'What if memory is strictly limited?'
3.Hash Set LookupOptimalO(N + M)O(N)Optimal linear time, clean and concise code.Gold standard optimal solution in interviews.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • No Common Elements (Disjoint Arrays) — Input: nums1 = [1, 2, 3], nums2 = [4, 5, 6], Expected: [] — Ensure your algorithm returns an empty array rather than null or an uninitialized buffer.
  • Heavy Duplicates in Input — Input: nums1 = [2, 2, 2, 2], nums2 = [2, 2, 2], Expected: [2] — The problem requires UNIQUE elements in the result. Output must contain 2 exactly once.
  • One Array is a Subset of the Other — Input: nums1 = [1, 2], nums2 = [1, 2, 3, 4, 5], Expected: [1, 2] — Always build the lookup set from the smaller array to minimize memory usage.
  • Single Element Arrays Matching vs Non-Matching — Input: nums1 = [5], nums2 = [5], Expected: [5] — Ensure single-element base cases terminate correctly without index out of bounds.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarification — Clarify whether the result needs to be sorted and whether duplicates should be preserved (Intersection I requires unique elements, whereas Intersection II preserves duplicate counts).
  2. Optimization Discussion — Proactively discuss the memory-time trade-off: 'We can achieve O(N + M) time with a Hash Set using O(min(N, M)) memory, or O(N log N + M log M) time with Two Pointers using O(1) memory.'
  3. Follow-Up Questions — Be ready for follow-ups: 'What if nums1's size is small compared to nums2's size?' (Binary search each element of nums1 in nums2) or 'What if elements are stored on disk and cannot fit in memory?' (External sort + two pointers).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Intersection of Two Arrays?

2.Why is the brute force approach suboptimal for large inputs in Intersection of Two Arrays?

3.Which data structure or technique enables the optimal solution for Intersection of Two Arrays?

Back to DSA Sheet