LeetCode 349: Intersection of Two Arrays

The 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 it in any order.

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

Input:  nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]      (order does not matter)

This looks trivial, and it is — which is exactly why it is a screening question. What is being tested is not whether you can produce an answer, but whether you reach for the right data structure without being told to.

#Clarify before you code

In a real interview, ask these first. Doing so is part of the assessment:

• Can the arrays be empty? Yes — return an empty array.
• Does output order matter? No, the problem says any order.
• Are duplicates allowed in the output? No — "each element must be unique." This is the constraint everyone misses.
• How large can the inputs be? LeetCode caps them at 1000, but ask anyway. It signals you are thinking about scale.
• Are they sorted? Not guaranteed. If they were, a better solution exists — mention it.

Then say what you are going to do before you write it. Interviewers are evaluating your reasoning; silent coding gives them nothing to evaluate.

#Solution 1 — brute force

Say this one out loud, then improve on it. Starting with the obvious approach and refining it is a positive signal, not a negative one.

def intersection(nums1, nums2):
    result = []
    for a in nums1:
        for b in nums2:
            if a == b and a not in result:
                result.append(a)
                break
    return result

It is correct. It is also the answer that ends the interview.

• Time: O(n × m) for the nested loops, and a not in result is itself a linear scan — so it is worse still.
• Space: O(min(n, m)) for the result.

The insight to voice: "I am scanning the whole of nums2 for every element of nums1. What I actually need is a fast membership test."

#Solution 2 — hash set

The moment the question is "is this value present?", the answer is a hash set. Lookups are O(1) instead of O(n).

def intersection(nums1, nums2):
    seen = set(nums1)
    result = set()

    for num in nums2:
        if num in seen:
            result.add(num)

    return list(result)

• Time: O(n + m) — one pass to build the set, one pass to check.
• Space: O(n) for the set.

This is the expected answer, and it is worth being able to explain why a set lookup is constant time: the value is hashed to an index and the bucket is checked directly, with no scanning. It is the single most useful data-structure fact in interviews.

Using a set for result handles the uniqueness requirement for free — no if x not in result check needed.

#Solution 3 — the one-liner

Python sets support real set algebra:

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

Same complexity as solution 2, one line. & is the intersection operator; | is union and - is difference.

Equivalents in other languages:

// JavaScript
const intersection = (a, b) => {
  const setB = new Set(b);
  return [...new Set(a)].filter(x => setB.has(x));
};

# Ruby
def intersection(nums1, nums2)
  nums1 & nums2      # Array#& already returns unique common elements
end

#Solution 4 — sorted input, two pointers

If the arrays arrive sorted, or if the interviewer asks for constant extra space, there is a better approach:

def intersection(nums1, nums2):
    nums1.sort()
    nums2.sort()

    i = j = 0
    result = []

    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            i += 1
        elif nums1[i] > nums2[j]:
            j += 1
        else:
            # Equal — record it, then skip past all duplicates on both sides
            if not result or result[-1] != nums1[i]:
                result.append(nums1[i])
            i += 1
            j += 1

    return result

• Time: O(n log n + m log m) if we must sort; O(n + m) if the input is already sorted.
• Space: O(1) beyond the output, if sorting in place.

The two-pointer technique — advance whichever pointer points at the smaller value — is worth internalising. It appears in merge intervals, merging sorted lists, three-sum, and a dozen other problems.

#Choosing between them

That last row is a good detail to raise unprompted. set(nums1) costs O(n) space; if nums1 has a million elements and nums2 has ten, build the set from nums2 instead. Same answer, a hundred thousand times less memory.

def intersection(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1     # always hash the smaller one
    seen = set(nums1)
    return list({num for num in nums2 if num in seen})

#The transferable lesson

Nested loop → hash lookup is the single most common optimisation in interview problems. It turns O(n²) into O(n) and it applies to a large family of questions:

• Two Sum — store each complement in a hash map as you go.
• Contains Duplicate — compare len(set(nums)) with len(nums).
• Longest Consecutive Sequence — a set makes "is n−1 present?" instant.
• Group Anagrams — a hash map keyed by the sorted letters.

Whenever you catch yourself writing for x in a: for y in b: and comparing, stop and ask what you would need to look up instead of scan. That question is most of what these problems are testing.

#Key takeaways

• Start brute force, state its complexity, then improve. The path is the point.
• "Is this value present?" always means hash set: O(1) instead of O(n).
• A set for results handles the uniqueness requirement with no extra code.
• Sorted input unlocks two pointers — O(n + m) time and O(1) extra space.
• Hash the smaller collection when the sizes are lopsided.