Intersection of Two Arrays

easy array hash set

Problem

Return the unique values that appear in both nums1 and nums2. Each value in the result must be unique; order does not matter.

Inputnums1 = [1, 2, 2, 1], nums2 = [2, 2]

Output[2]

Hash nums1 into a set, then collect values from nums2 that hit.

nums1

nums2

def intersection(nums1, nums2):
    a = set(nums1)
    out = set()
    for x in nums2:
        if x in a:
            out.add(x)
    return list(out)

function intersection(nums1, nums2) {
  const a = new Set(nums1);
  const out = new Set();
  for (const x of nums2) {
    if (a.has(x)) out.add(x);
  }
  return [...out];
}

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> a = new HashSet<>();
        for (int x : nums1) a.add(x);
        Set<Integer> out = new HashSet<>();
        for (int x : nums2) if (a.contains(x)) out.add(x);
        return out.stream().mapToInt(Integer::intValue).toArray();
    }
}

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

Explanation

We want the unique values present in both arrays. A hash set makes membership tests instant, which is exactly what we need to check "does this value also appear in the other array?"

So we pour all of nums1 into a set a (duplicates collapse automatically). Then we walk nums2 and, for each value, ask if x in a. Every hit goes into a second set out.

Using a set for the output guarantees each value appears at most once, even if nums2 repeats it.

Example: nums1 = [1, 2, 2, 1] becomes the set {1, 2}. Scanning nums2 = [2, 2]: the first 2 is in the set so it is added; the second 2 is already in out, so nothing changes. Result [2].

Both passes are linear, so the whole thing runs in time proportional to the two array lengths.

Time: O(n + m) Space: O(min(n, m))