Intersection of Two Arrays

Intersection of Two Arrays easy

Description

Given two integer arrays nums1 and nums2, return their intersection as an array. Each element in the result must be unique, and you may return the result in any order.

Examples

> Case 1:
    nums1 = [1, 2, 2, 1],   nums2 = [2, 2]
    Output: [2]
 
> Case 2:
    nums1 = [4, 9, 5],      nums2 = [9, 4, 9, 8, 4]
    Output: [9, 4]      (or [4, 9])

Constraints

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

Try it yourself

The two-set one-liner returns elements in an arbitrary order, which is hard to test against a fixed expected list. So this challenge uses the sort + two-pointer version, which returns the unique intersection in ascending order.

⌨ Intersection of Two Arrays — return unique shared values (sorted)

def intersection(nums1, nums2):
  # sort both, then walk two pointers; collect each shared value once
  pass

Hint

Sort both arrays. Advance the pointer at the smaller value; when they're equal, record it once (skip if it equals the last recorded value) and advance both.

Reveal solution

Approach 1: Two sets — the canonical answer

Convert one array to a set, then iterate the other and collect elements that are in the set.

Time O(n + m), space O(n) for the smaller-array set.

Approach 2: Sort + two pointers

If you can’t use extra hash-map memory (or the arrays are already sorted), use two pointers.

Time O(n log n + m log m), space depends on the sort (O(1) for in-place quicksort).

Approach comparison

Approach	Time	Space	When to pick
Two sets	O(n + m)	O(min(n, m))	Default — simpler and faster
Sort + two pointers	O(n log n + m log m)	O(1) extra	When arrays are already sorted, or you need to avoid hash memory

For the given constraints (n, m ≤ 1000), both work in microseconds. In a real interview, mention both — and explain why two sets is the better default.

The “convert one collection to a set, scan the other” pattern is one of the most common hash-map plays. Same shape solves: Intersection of Two Arrays II (with duplicates), Common Words in 3 Strings, Find Duplicates in Two Sorted Streams. The hash set gives you O(1) “is this in the other collection?”

Variant: Intersection of Two Arrays II (keep duplicates)

If duplicates count ([1,2,2,1] ∩ [2,2] = [2,2] instead of [2]), use a counter instead of a set:

from collections import Counter
def intersect(nums1, nums2):
    c1 = Counter(nums1)
    result = []
    for x in nums2:
        if c1[x] > 0:
            result.append(x)
            c1[x] -= 1
    return result

The counter tracks remaining capacity per value. Each match decrements; when capacity hits zero, no more matches for that value.

Analysis

Time: O(n + m) with the two-set approach.
Space: O(min(n, m)) — we only need to store the smaller array’s set.

First Unique Character Happy Number

Finished this page?