Problem statement

Given two integer arrays nums1 and nums2, return an array of their intersection: each element that appears in both arrays, listed once, in increasing order.

Example 1

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Explanation: 2 is common; it is reported once even though it repeats.

Example 2

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

Example 3

Input: nums1 = [1,2], nums2 = [3,4]
Output: []

Constraints

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

Hints for Intersection of Two Arrays

1. Hint 1

   Put one array into a hash set so membership is O(1).

2. Hint 2

   Collect the hits into a second set — that is what removes duplicates.

3. Hint 3

   Sort at the end, since the answer must come back in increasing order.

How to solve Intersection of Two Arrays

Turn both arrays into sets, intersect them, and sort the result.

Approach

1. Build a set from each array.
2. Take the intersection.
3. Sort and return.

Why it works

Sets discard duplicates, which is exactly the "listed once" requirement, and the intersection keeps a value only if both arrays contain it.

Complexity

• Time — O(n + m + k log k) where k is the answer size
• Space — O(n + m)

Pitfalls

• Without a set for the hits, a value present twice in the second array is reported twice.
• The answer must be sorted — hash-set iteration order is arbitrary.

Reference solution

Python

def intersection(nums1, nums2):
    return sorted(set(nums1) & set(nums2))

Java

public static int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> inB = new HashSet<>();
    for (int x : nums2) inB.add(x);
    TreeSet<Integer> out = new TreeSet<>();
    for (int x : nums1) {
        if (inB.contains(x)) out.add(x);
    }
    int[] res = new int[out.size()];
    int i = 0;
    for (int x : out) res[i++] = x;
    return res;
}

C++

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> inB(nums2.begin(), nums2.end());
    set<int> out;
    for (int x : nums1) {
        if (inB.count(x)) out.insert(x);
    }
    return vector<int>(out.begin(), out.end());
}

JavaScript

var intersection = function(nums1, nums2) {
    const setB = new Set(nums2);
    const out = new Set();
    for (let i = 0; i < nums1.length; i++) {
        if (setB.has(nums1[i])) out.add(nums1[i]);
    }
    return Array.from(out).sort(function(a, b) { return a - b; });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy