349. Intersection of Two Arrays (Easy)

Problem

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

• nums1 = [1,2,2,1], nums2 = [2,2] → [2]
• nums1 = [4,9,5], nums2 = [9,4,9,8,4] → [9,4]

LeetCode 349 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach: Set intersection

Convert both arrays to sets (deduplication in $O(n)$), then compute the intersection using Python’s & operator.

Python

def intersection(nums1: list[int], nums2: list[int]) -> list[int]:
    s1 = set(nums1)          # L1: O(m) build set from nums1
    s2 = set(nums2)          # L2: O(n) build set from nums2
    return list(s1 & s2)     # L3: O(min(m, n)) intersection, O(k) list convert

Or collapsed to one line (equivalent, same complexity):

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

TypeScript

function intersection(nums1: number[], nums2: number[]): number[] {
    const s1 = new Set(nums1);          // L1: O(m) build set from nums1
    const s2 = new Set(nums2);          // L2: O(n) build set from nums2
    return [...s1].filter(x => s2.has(x)); // L3: O(min(m, n)) intersection
}

Where the time goes, line by line

Variables: m = len(nums1), n = len(nums2), k = size of intersection.

Line	Per-call cost	Times executed	Contribution
L1 (set(nums1))	$O(m)$	1	$O(m)$
L2 (set(nums2))	$O(n)$	1	$O(n)$
L3 (intersection + list)	$O(min(m, n)$)	1	$O(min(m, n)$)

Building both sets dominates. The & operation iterates the smaller set and checks membership in the larger (hash lookup, $O(1)$ average per element).

Complexity

• Time: $O(m + n)$, driven by L1/L2 (constructing the two sets).
• Space: $O(m + n)$ in the worst case, storing both sets plus the result.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        Array(Set(nums1).intersection(Set(nums2))).sorted()
    }
}

Why sets work here

The problem says each element in the result must be unique. Sets enforce uniqueness automatically: set([2,2]) is {2}. The & operator then finds common elements across two sets of distinct values, so no deduplication is needed on the output.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_349.py and run.

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

def _run_tests():
    assert sorted(intersection([1,2,2,1], [2,2])) == [2]
    assert sorted(intersection([4,9,5], [9,4,9,8,4])) == [4, 9]
    assert intersection([1,2,3], [4,5,6]) == []
    assert sorted(intersection([1,1,1], [1,1,1])) == [1]
    assert sorted(intersection([1,2,3,4,5], [3,4,5,6,7])) == [3, 4, 5]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function assert(condition: boolean, msg: string = ''): void {
    if (!condition) throw new Error(msg || 'Assertion failed');
}

function intersection(nums1: number[], nums2: number[]): number[] {
    const s1 = new Set(nums1);
    const s2 = new Set(nums2);
    return [...s1].filter(x => s2.has(x));
}

assert(JSON.stringify([...intersection([1,2,2,1], [2,2])].sort()) === JSON.stringify([2]));
assert(JSON.stringify([...intersection([4,9,5], [9,4,9,8,4])].sort()) === JSON.stringify([4,9]));
assert(intersection([1,2,3], [4,5,6]).length === 0);
assert(JSON.stringify(intersection([1,1,1], [1,1,1])) === JSON.stringify([1]));
assert(JSON.stringify([...intersection([1,2,3,4,5], [3,4,5,6,7])].sort()) === JSON.stringify([3,4,5]));
console.log("all tests pass");

Related topics

• Two Sum, set/hash-map pattern for complement lookup
• Contains Duplicate, single-set membership check
• Group Anagrams, grouping elements by a hash key

Related concepts

• Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.
• Sorting as Preprocessing, the order first tactic that exposes adjacency, sweep boundaries, and duplicate control.