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.

Core Insight for Intersection of Two Arrays

The key intuition for solving LeetCode 349 efficiently lies in the properties of sorted arrays.

If nums1 and nums2 are unsorted, we have no context about where a matching number might be located. However, if we sort both arrays first, we establish a monotonic order. This allows us to apply the Two Pointer strategy:

1. Relative Magnitude: If nums1[i] is smaller than nums2[j], we know for certain that nums1[i] cannot equal nums2[j] or any subsequent element in nums2 (since nums2 is sorted). Therefore, we must increment index i to find a larger candidate.
2. Equality: If nums1[i] equals nums2[j], we have found an intersection. We record it and verify uniqueness.
3. Invariant: At any step, we only discard elements that are strictly smaller than the current candidate in the opposing array, ensuring we never miss a valid intersection.

Visual Description: Imagine two horizontal number lines representing the sorted arrays. We place a marker (pointer) at the start of each line. We compare the values under the markers. The marker pointing to the smaller value moves one step to the right. If they are equal, we record the value and move both markers. This process continues until one marker runs off the end of its line.

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.

Reference Implementation

C++ Solution for LeetCode 349

cpp
#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
        // Step 1: Sort both arrays
        std::sort(nums1.begin(), nums1.end());
        std::sort(nums2.begin(), nums2.end());
        
        std::vector<int> result;
        int i = 0; // Pointer for nums1
        int j = 0; // Pointer for nums2
        
        // Step 2: Traverse with two pointers
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                // Found intersection
                // Ensure uniqueness: add only if result is empty or last element is different
                if (result.empty() || result.back() != nums1[i]) {
                    result.push_back(nums1[i]);
                }
                i++;
                j++;
            }
        }
        
        return result;
    }
};

Java Solution for LeetCode 349

java
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // Step 1: Sort both arrays
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        List<Integer> resultList = new ArrayList<>();
        int i = 0;
        int j = 0;
        
        // Step 2: Traverse with two pointers
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                // Found intersection
                // Handle uniqueness
                if (resultList.isEmpty() || resultList.get(resultList.size() - 1) != nums1[i]) {
                    resultList.add(nums1[i]);
                }
                i++;
                j++;
            }
        }
        
        // Convert List to array
        int[] result = new int[resultList.size()];
        for (int k = 0; k < resultList.size(); k++) {
            result[k] = resultList.get(k);
        }
        
        return result;
    }
}

Python Solution for LeetCode 349

python
class Solution:
    def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
        # Step 1: Sort both arrays
        nums1.sort()
        nums2.sort()
        
        result = []
        i, j = 0, 0
        
        # Step 2: Traverse with two pointers
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                # Found intersection
                # Handle uniqueness
                if not result or result[-1] != nums1[i]:
                    result.append(nums1[i])
                i += 1
                j += 1
                
        return result

Q: Why is my solution slower than expected? Mistake: Using .contains() on a List inside the loop to check for uniqueness. Why: The .contains() method on a List is $O(N)$. Doing this inside the loop makes the total complexity $O(N^2)$. Consequence: Efficiency failure. By sorting first, checking uniqueness only requires comparing against the last added element, which is $O(1)$.