Intersection of Two Arrays

LeetCode 349: Intersection of Two Arrays Solution & Explanation

Problem Overview

TL;DR: Sort both input arrays and iterate through them simultaneously using two pointers to identify and collect unique common elements.

The Intersection of Two Arrays problem requires us to find common elements between two integer arrays, nums1 and nums2. The resulting array must contain unique elements only, meaning if a number appears multiple times in the intersection, it should only appear once in the output. The order of the result does not matter. This is a fundamental LeetCode 349 solution scenario often used to test understanding of array manipulation and memory efficiency.

Brute Force Approach for Intersection of Two Arrays

The naive approach involves iterating through every element of the first array and, for each element, scanning the entire second array to check for a match. To ensure uniqueness, we would store matches in a set (or check the result list before adding).

Pseudo-code:

result = empty set
for each x in nums1:
    for each y in nums2:
        if x == y:
            add x to result
return list(result)

Time Complexity: $O(N \times M)$, where $N$ and $M$ are the lengths of the arrays. For every element in $N$, we scan $M$. Why it fails: While this might pass for small constraints (like $N=1000$), it is inefficient. In an interview context, an $O(N \times M)$ quadratic solution is rarely considered acceptable when linear or log-linear solutions exist. It demonstrates a lack of algorithmic optimization knowledge.

Algorithm Strategy: Two Pointer Patterns

1. Sort Inputs: Begin by sorting both nums1 and nums2 in ascending order. This is a prerequisite for the two-pointer logic to work.
2. Initialize Pointers: Set two pointers, i and j, to 0. These correspond to the indices of nums1 and nums2 respectively.
3. Traverse and Compare: Enter a loop that continues as long as both i and j are within the bounds of their respective arrays.
   • If nums1[i] < nums2[j]: Increment i.
   • If nums1[i] > nums2[j]: Increment j.
   • If nums1[i] == nums2[j]: This is an intersection. Check if the result array is empty or if the last added element is different from nums1[i] (to ensure uniqueness). If unique, add it to the result. Increment both i and j.
4. Return: Convert the result collection to the required return type (array/vector).

Execution Flow

Let's trace nums1 = [4, 9, 5] and nums2 = [9, 4, 9, 8, 4].

1. Sort:
   • nums1 becomes [4, 5, 9]
   • nums2 becomes [4, 4, 8, 9, 9]
2. State: i = 0, j = 0, result = []
3. Iteration 1:
   • Compare nums1[0] (4) and nums2[0] (4).
   • They are equal. Add 4 to result.
   • Increment i to 1, j to 1.
   • result = [4]
4. Iteration 2:
   • Compare nums1[1] (5) and nums2[1] (4).
   • 5 > 4. Increment j to 2.
5. Iteration 3:
   • Compare nums1[1] (5) and nums2[2] (8).
   • 5 < 8. Increment i to 2.
6. Iteration 4:
   • Compare nums1[2] (9) and nums2[2] (8).
   • 9 > 8. Increment j to 3.
7. Iteration 5:
   • Compare nums1[2] (9) and nums2[3] (9).
   • They are equal. Check uniqueness. 9 != last element (4). Add 9.
   • Increment i to 3, j to 4.
   • result = [4, 9]
8. Termination: i is now 3, which equals the length of nums1. The loop terminates. Return [4, 9].

Proof of Correctness

The algorithm relies on the monotonicity of the sorted arrays. When nums1[i] < nums2[j], the value nums1[i] cannot exist in nums2 at any index k >= j because nums2 is sorted in ascending order. Therefore, skipping nums1[i] is safe. The same logic applies when nums2[j] < nums1[i]. When values are equal, we capture the intersection. Since we iterate through the sorted arrays linearly and only skip elements that cannot possibly match, the algorithm is guaranteed to find all common elements. The uniqueness check ensures adherence to the problem constraints.

Pattern Reuse Notes

The Two Pointer pattern used here is highly versatile. The following problems share the same underlying logic of manipulating pointers on sorted arrays or converging boundaries:

• LeetCode 11: Container With Most Water (Converging pointers to optimize area)
• LeetCode 15: 3Sum (Sorting + Two Pointers to find triplets)
• LeetCode 16: 3Sum Closest (Variation of 3Sum using distance comparison)
• LeetCode 18: 4Sum (Extension of 3Sum logic)

Understanding how sorting enables deterministic pointer movement is key to solving these popular interview questions.

Reference Implementation

C++ Solution for LeetCode 349

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
7        // Step 1: Sort both arrays
8        std::sort(nums1.begin(), nums1.end());
9        std::sort(nums2.begin(), nums2.end());
10        
11        std::vector<int> result;
12        int i = 0; // Pointer for nums1
13        int j = 0; // Pointer for nums2
14        
15        // Step 2: Traverse with two pointers
16        while (i < nums1.size() && j < nums2.size()) {
17            if (nums1[i] < nums2[j]) {
18                i++;
19            } else if (nums1[i] > nums2[j]) {
20                j++;
21            } else {
22                // Found intersection
23                // Ensure uniqueness: add only if result is empty or last element is different
24                if (result.empty() || result.back() != nums1[i]) {
25                    result.push_back(nums1[i]);
26                }
27                i++;
28                j++;
29            }
30        }
31        
32        return result;
33    }
34};

Java Solution for LeetCode 349

1import java.util.Arrays;
2import java.util.ArrayList;
3import java.util.List;
4
5class Solution {
6    public int[] intersection(int[] nums1, int[] nums2) {
7        // Step 1: Sort both arrays
8        Arrays.sort(nums1);
9        Arrays.sort(nums2);
10        
11        List<Integer> resultList = new ArrayList<>();
12        int i = 0;
13        int j = 0;
14        
15        // Step 2: Traverse with two pointers
16        while (i < nums1.length && j < nums2.length) {
17            if (nums1[i] < nums2[j]) {
18                i++;
19            } else if (nums1[i] > nums2[j]) {
20                j++;
21            } else {
22                // Found intersection
23                // Handle uniqueness
24                if (resultList.isEmpty() || resultList.get(resultList.size() - 1) != nums1[i]) {
25                    resultList.add(nums1[i]);
26                }
27                i++;
28                j++;
29            }
30        }
31        
32        // Convert List to array
33        int[] result = new int[resultList.size()];
34        for (int k = 0; k < resultList.size(); k++) {
35            result[k] = resultList.get(k);
36        }
37        
38        return result;
39    }
40}

Python Solution for LeetCode 349

1class Solution:
2    def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
3        # Step 1: Sort both arrays
4        nums1.sort()
5        nums2.sort()
6        
7        result = []
8        i, j = 0, 0
9        
10        # Step 2: Traverse with two pointers
11        while i < len(nums1) and j < len(nums2):
12            if nums1[i] < nums2[j]:
13                i += 1
14            elif nums1[i] > nums2[j]:
15                j += 1
16            else:
17                # Found intersection
18                # Handle uniqueness
19                if not result or result[-1] != nums1[i]:
20                    result.append(nums1[i])
21                i += 1
22                j += 1
23                
24        return result