Intersection of Two Arrays

Problem Statement

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear only once, and the result can be in any order.

What to notice first

• The result requires unique values — even if a number appears multiple times in both arrays, it appears only once in the output.
• The hash set approach is fastest when the arrays are unsorted or of different sizes.
• The two-pointer approach shines when the input is already sorted or when no extra memory is available.

Examples

nums1	nums2	Output	Explanation
[1, 2, 2, 1]	[2, 2]	[2]	2 is common; duplicates collapsed
[4, 9, 5]	[9, 4, 9, 8, 4]	[9, 4]	9 and 4 are common

Constraints

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

Real-World Applications

Where this pattern appears

• Friend suggestions — find users that two people both follow.
• Tag matching — find categories that two documents share.
• Inventory cross-check — find product SKUs that appear in both a purchase order and a warehouse manifest.
• DNS cache deduplication — find hostnames resolved by both of two DNS resolvers over a time window.

Complexity Comparison

Approach	Time	Space	Best When
Hash Set	O(n + m)	O(min(n, m))	Unsorted arrays; fast lookup
Two Pointers	O(n log n + m log m)	O(1)*	Arrays are already sorted or memory is scarce

* O(1) extra space beyond the output array (sort is in-place).

Which approach should you learn first?

• Learn Hash Set first — it is the faster approach for unsorted inputs and the standard expectation in interviews.
• Learn Two Pointers as a follow-up — it demonstrates the general sorted-merge pattern used across many problems.

Best For Speed

Hash Set

O(n+m) time · O(min(n,m)) space

No Extra Memory

Two Pointers

O(n log n + m log m) time · O(1) space

Approach 1: Hash Set

★ Recommended

Convert nums1 into a set to deduplicate it. Scan nums2 and collect every element that is in the set into a result set (to prevent duplicates in the output). Convert the result set to a list.

⏱ Time O(n + m) One pass each 💾 Space O(min(n, m)) Set of the smaller array

Step-by-step Example

Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]

Phase	Action	Result set
Build set from nums1	{4, 9, 5}	—
Check 9 from nums2	9 ∈ set1	{9}
Check 4 from nums2	4 ∈ set1	{9, 4}
Check 9 again	Already in result	{9, 4}
Check 8	8 ∉ set1	{9, 4}
Check 4 again	Already in result	{9, 4}
Return		[9, 4]

Animated walkthrough

How the hash set finds the unique intersection

Use Next or Autoplay to see nums1 converted to a lookup set, then nums2 scanned for matches.

Back Autoplay Next Reset

Step 1 of 4

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function intersection(nums1, nums2):
    set1 = set(nums1)
    result = set()
    for num in nums2:
        if num in set1:
            result.add(num)
    return list(result)

Solution Code

Python

intersection_of_two_arrays_hash_set.py

from typing import List


def intersection(nums1: List[int], nums2: List[int]) -> List[int]:
    return list(set(nums1) & set(nums2))

C++

intersection_of_two_arrays_hash_set.cpp

#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> seen(nums1.begin(), nums1.end());
        unordered_set<int> result;
        for (int num : nums2) {
            if (seen.count(num)) result.insert(num);
        }
        return vector<int>(result.begin(), result.end());
    }
};

Java

intersection_of_two_arrays_hash_set.java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> result = new HashSet<>();
        for (int num : nums1) set1.add(num);
        for (int num : nums2) {
            if (set1.contains(num)) result.add(num);
        }
        int[] output = new int[result.size()];
        int index = 0;
        for (int num : result) output[index++] = num;
        return output;
    }
}

JavaScript

intersection_of_two_arrays_hash_set.js

function intersection(nums1, nums2) {
    const set1 = new Set(nums1);
    const set2 = new Set(nums2);
    return [...set1].filter((num) => set2.has(num));
}

Rust

intersection_of_two_arrays_hash_set.rs

use std::collections::HashSet;

impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let seen: HashSet<i32> = nums1.into_iter().collect();
        let mut result = HashSet::new();
        for num in nums2 {
            if seen.contains(&num) {
                result.insert(num);
            }
        }
        result.into_iter().collect()
    }
}

Go

intersection_of_two_arrays_hash_set.go

func intersection(nums1 []int, nums2 []int) []int {
    seen := map[int]bool{}
    result := map[int]bool{}
    for _, num := range nums1 {
        seen[num] = true
    }
    for _, num := range nums2 {
        if seen[num] {
            result[num] = true
        }
    }
    output := make([]int, 0, len(result))
    for num := range result {
        output = append(output, num)
    }
    return output
}

Approach 2: Two Pointers

🎯 Interview Favourite

Sort both arrays. Use two pointers starting at the beginning of each. Advance the pointer pointing to the smaller value. When both pointers point to equal values, record the result (skipping consecutive duplicates) and advance both.

⏱ Time O(n log n + m log m) Sort dominates 💾 Space O(1) In-place sort, no extra structure

Step-by-step Example

Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]

After sorting: nums1 = [4, 5, 9], nums2 = [4, 4, 8, 9, 9]

i	j	nums1[i]	nums2[j]	Action	result
0	0	4	4	Equal → add, both++	[4]
1	2	5	8	5 < 8 → i++	[4]
2	2	9	8	9 > 8 → j++	[4]
2	3	9	9	Equal → add, both++	[4, 9]
3	5	—	—	Done	[4, 9]

Pseudocode

function intersection(nums1, nums2):
    sort(nums1); sort(nums2)
    result = []
    i, j = 0, 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            if not result or result[-1] != nums1[i]:
                result.append(nums1[i])
            i++; j++
        elif nums1[i] < nums2[j]:
            i++
        else:
            j++
    return result

Solution Code

Python

intersection_of_two_arrays_two_pointer.py

from typing import List


def intersection(nums1: List[int], nums2: List[int]) -> List[int]:
    nums1.sort()
    nums2.sort()
    result = []
    i, j = 0, 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            if not result or result[-1] != nums1[i]:
                result.append(nums1[i])
            i += 1
            j += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return result


print(intersection([4, 9, 5], [9, 4, 9, 8, 4]))  # [4, 9]
print(intersection([1, 2, 2, 1], [2, 2]))          # [2]

C++

intersection_of_two_arrays_two_pointer.cpp

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> result;
        int i = 0, j = 0;
        while (i < (int)nums1.size() && j < (int)nums2.size()) {
            if (nums1[i] == nums2[j]) {
                if (result.empty() || result.back() != nums1[i])
                    result.push_back(nums1[i]);
                i++; j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return result;
    }
};

Java

intersection_of_two_arrays_two_pointer.java

import java.util.*;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> result = new ArrayList<>();
        int i = 0, j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                if (result.isEmpty() || result.get(result.size() - 1) != nums1[i])
                    result.add(nums1[i]);
                i++; j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        return result.stream().mapToInt(x -> x).toArray();
    }
}

JavaScript

intersection_of_two_arrays_two_pointer.js

function intersection(nums1, nums2) {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);
    const result = [];
    let i = 0, j = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] === nums2[j]) {
            if (!result.length || result[result.length - 1] !== nums1[i])
                result.push(nums1[i]);
            i++; j++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}

Rust

intersection_of_two_arrays_two_pointer.rs

impl Solution {
    pub fn intersection(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> Vec<i32> {
        nums1.sort_unstable();
        nums2.sort_unstable();
        let mut result: Vec<i32> = Vec::new();
        let (mut i, mut j) = (0usize, 0usize);
        while i < nums1.len() && j < nums2.len() {
            match nums1[i].cmp(&nums2[j]) {
                std::cmp::Ordering::Equal => {
                    if result.last() != Some(&nums1[i]) {
                        result.push(nums1[i]);
                    }
                    i += 1;
                    j += 1;
                }
                std::cmp::Ordering::Less => i += 1,
                std::cmp::Ordering::Greater => j += 1,
            }
        }
        result
    }
}

Go

intersection_of_two_arrays_two_pointer.go

package golang
import "sort"

func intersection(nums1 []int, nums2 []int) []int {
  sort.Ints(nums1)
  sort.Ints(nums2)
  result := []int{}
















}  return result  }    }      j++    } else {      i++    } else if nums1[i] < nums2[j] {      j++      i++      }        result = append(result, nums1[i])      if len(result) == 0 || result[len(result)-1] != nums1[i] {    if nums1[i] == nums2[j] {  for i < len(nums1) && j < len(nums2) {  i, j := 0, 0

Watch for these pitfalls

• Forgetting to deduplicate: if the same value appears in both arrays multiple times, both approaches must ensure it appears only once in the output — the hash set does this automatically, but the two-pointer approach needs an explicit skip.
• Sorting modifies the input arrays — if the caller needs the original order, sort copies instead.
• Confusing this problem (#349, unique intersection) with #350 (Intersection of Two Arrays II), which allows duplicates in the result.

Approach 3: Optimized Two-Pointer

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

intersection_of_two_arrays_optimized.py

"""
Solution for Intersection of Two Arrays
"""

def solve():
    """Implementation for approach 3 of Intersection of Two Arrays"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

intersection_of_two_arrays_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Intersection of Two Arrays
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

IntersectionOfTwoArraysOptimized.java

/**
 * Solution for Intersection of Two Arrays
 * Approach 3
 */
public class IntersectionOfTwoArraysOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

intersection_of_two_arrays_optimized.js

/**
 * Solution for Intersection of Two Arrays
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

intersection_of_two_arrays_optimized.rs

/// Solution for Intersection of Two Arrays
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

intersection_of_two_arrays_optimized.go

package main

import "fmt"

// Solution for Intersection of Two Arrays
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Two Sum Easy #1
• Contains Duplicate Easy #217
• Intersection of Two Arrays II ↗ Easy #350
• Two Sum Easy #1

Interview Tips

Key trade-offs to discuss

• Hash set vs two pointers: hash set wins on speed (O(n+m)), two pointers wins on space (O(1) extra). Know when to use each.
• Follow-up — if one array is very large and the other is small? Build the set from the smaller array to minimise memory.
• Follow-up — if the arrays are already sorted? Skip the sort cost and go directly to the two-pointer scan.
• Follow-up — intersection with duplicates (#350)? Replace the result set with a frequency map and take the minimum count of each common element.

← Previous
#347 Top K Frequent Elements Next
#373 Find K Pairs with Smallest Sums →