LeetCode 349 - Intersection of Two Arrays

LeetCode Problem 349

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem gives us two integer arrays, nums1 and nums2, and asks us to return their intersection. The intersection consists of all values that appear in both arrays. However, the result must contain only unique elements, even if a number appears many times in either array.

For example, if nums1 = [1,2,2,1] and nums2 = [2,2], the number 2 appears in both arrays, so the answer is [2]. Even though 2 appears multiple times, it should only appear once in the result.

The input arrays can contain duplicate values, but duplicates are irrelevant in the final output because uniqueness is required. The order of the output does not matter, which gives us flexibility in how we construct the result.

The constraints are relatively small, with both arrays having at most 1000 elements. This means even slower approaches could technically pass, but the problem is designed to test efficient use of hash tables, sorting, or two pointers.

Several edge cases are important to recognize:

• Arrays may contain many duplicates, so we must avoid returning repeated values.
• One array may contain elements that never appear in the other array.
• The intersection may contain only a single value.
• The arrays may already be unique, or they may contain all identical values.
• Since the values are limited to the range [0, 1000], there are no concerns about integer overflow or extremely large numbers.

The key requirement is uniqueness, which means we need a reliable way to track whether we have already added a value to the answer.

Approaches

Brute Force Approach

A straightforward solution is to compare every element in nums1 with every element in nums2.

For each number in nums1, we scan through nums2 to see whether the value exists there. If it does, we add it to the result if it has not already been added.

This approach works because every possible pair is checked, guaranteeing that any common element will eventually be found. However, the nested iteration makes the algorithm inefficient.

If n is the length of nums1 and m is the length of nums2, then this approach takes O(n * m) time. While the constraints are small enough for this to pass, it becomes unnecessarily slow for larger inputs.

Optimal Approach

The key observation is that we only need fast membership checking.

A hash set provides average O(1) lookup time. By storing all elements of one array in a set, we can quickly determine whether an element from the other array exists in it.

The algorithm becomes:

1. Convert one array into a set.
2. Iterate through the second array.
3. If a value exists in the set, add it to the result set.
4. Convert the result set into a list.

Using sets automatically removes duplicates, which perfectly matches the problem requirement.

This reduces the time complexity to linear time relative to the size of the input arrays.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(k)	Compares every pair of elements, inefficient for large inputs
Optimal	O(n + m)	O(n + k)	Uses hash sets for fast lookup and automatic uniqueness

Here, k represents the number of unique elements in the intersection.

Algorithm Walkthrough

1. Create a set from nums1.

A set allows constant average time membership checking. This means we can quickly determine whether a value from nums2 exists in nums1. 2. Create an empty result set.

Since the problem requires unique intersection values, a set is the ideal structure for storing the answer. Even if we encounter the same value multiple times, it will only appear once in the result set. 3. Iterate through each number in nums2.

For every value, check whether it exists in the set created from nums1. 4. If the value exists in the first set, add it to the result set.

This confirms the value appears in both arrays. 5. Convert the result set into a list and return it.

The problem expects an array-like structure as output, so we convert the set back into a list before returning.

Why it works

The algorithm works because a value belongs in the intersection if and only if it appears in both arrays. The first set records all unique values from nums1. During iteration over nums2, every lookup checks whether the current value also exists in nums1.

Using a result set guarantees uniqueness automatically. Therefore, every returned value appears in both arrays exactly once, which satisfies the problem requirements.

Python Solution

from typing import List

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1_set = set(nums1)
        intersection_set = set()

        for num in nums2:
            if num in nums1_set:
                intersection_set.add(num)

        return list(intersection_set)

The implementation starts by converting nums1 into a set called nums1_set. This preprocessing step enables fast membership checks.

Next, the code initializes intersection_set, which stores the unique intersection values.

The loop iterates through every value in nums2. For each number, the condition if num in nums1_set checks whether the value exists in the first array. If it does, the value is added to intersection_set.

Finally, the set is converted into a list because LeetCode expects a list return type.

The implementation directly mirrors the algorithm walkthrough and leverages Python's built in set operations for concise and efficient code.

Go Solution

func intersection(nums1 []int, nums2 []int) []int {
    nums1Set := make(map[int]bool)
    resultSet := make(map[int]bool)

    for _, num := range nums1 {
        nums1Set[num] = true
    }

    for _, num := range nums2 {
        if nums1Set[num] {
            resultSet[num] = true
        }
    }

    result := []int{}

    for num := range resultSet {
        result = append(result, num)
    }

    return result
}

Go does not have a built in set type, so maps are commonly used to simulate sets. In this solution, map[int]bool is used to track membership.

The first map stores all values from nums1, while the second map stores the intersection values uniquely.

Unlike Python, Go requires explicit slice creation and appending when constructing the final result. Otherwise, the overall logic remains the same.

There are no concerns about integer overflow because the constraints are small and Go's int type easily handles the input range.

Worked Examples

Example 1

Input:

nums1 = [1,2,2,1]
nums2 = [2,2]

First, create the set from nums1.

nums1_set = {1, 2}

Initialize:

intersection_set = {}

Now iterate through nums2.

Current Number	Exists in nums1_set?	intersection_set
2	Yes	{2}
2	Yes	{2}

The final result is:

[2]

Example 2

Input:

nums1 = [4,9,5]
nums2 = [9,4,9,8,4]

Create the set from nums1.

nums1_set = {4, 5, 9}

Initialize:

intersection_set = {}

Iterate through nums2.

Current Number	Exists in nums1_set?	intersection_set
9	Yes	{9}
4	Yes	{9, 4}
9	Yes	{9, 4}
8	No	{9, 4}
4	Yes	{9, 4}

The final result is:

[9, 4]

The order may vary because sets do not preserve insertion order.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Building the first set takes O(n), iterating through the second array takes O(m)
Space	O(n + k)	The first set stores unique elements from nums1, the result set stores intersection values

The time complexity is linear because each element is processed a constant number of times. Set membership checking is average O(1).

The space complexity depends on the number of unique values stored in the sets. In the worst case, all elements are distinct.

Test Cases

sol = Solution()

# Provided example with duplicates
assert sorted(sol.intersection([1,2,2,1], [2,2])) == [2]

# Provided example with multiple intersections
assert sorted(sol.intersection([4,9,5], [9,4,9,8,4])) == [4,9]

# No common elements
assert sorted(sol.intersection([1,2,3], [4,5,6])) == []

# Identical arrays
assert sorted(sol.intersection([1,2,3], [1,2,3])) == [1,2,3]

# One common element repeated many times
assert sorted(sol.intersection([1,1,1,1], [1,1])) == [1]

# Single element arrays with match
assert sorted(sol.intersection([5], [5])) == [5]

# Single element arrays without match
assert sorted(sol.intersection([5], [6])) == []

# One array completely contained in the other
assert sorted(sol.intersection([1,2,3,4], [2,3])) == [2,3]

# Large amount of duplicates
assert sorted(sol.intersection([2]*1000, [2]*1000)) == [2]

# Multiple duplicates with several unique intersections
assert sorted(sol.intersection([1,2,2,3,4], [2,2,4,4,5])) == [2,4]

Test	Why
[1,2,2,1] and [2,2]	Validates duplicate handling
[4,9,5] and [9,4,9,8,4]	Validates multiple intersection values
[1,2,3] and [4,5,6]	Validates empty intersection
Identical arrays	Ensures all unique values are returned
Repeated single value	Ensures duplicates appear only once
Single element match	Smallest successful case
Single element mismatch	Smallest unsuccessful case
One array contained in another	Tests subset behavior
1000 repeated values	Stress test for duplicates
Multiple duplicate intersections	Validates uniqueness across several values

Edge Cases

One important edge case occurs when both arrays contain many duplicates of the same value. A naive implementation might accidentally add the same number multiple times to the result. Using a set for the result prevents this issue automatically because sets store only unique elements.

Another edge case happens when the arrays have no common elements. In this scenario, the algorithm should return an empty list. Since values are only added when membership exists in the first set, the result set remains empty and converts cleanly into an empty list.

A third important case is when one array is entirely contained within the other. For example, nums1 = [1,2,3,4] and nums2 = [2,3]. The algorithm correctly identifies both 2 and 3 as common elements because every value in the smaller array is checked independently against the set.

A final edge case involves arrays of length one. Small inputs often expose off by one errors or incorrect initialization. The implementation handles these correctly because the logic does not depend on array size, every element is processed uniformly through the same set lookup mechanism.