The Two Sum Pattern

Concept

LeetCode #1. Two Sum.
Problem: Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
nums = [2, 7, 11, 15], target = 9. Output: [0, 1] (Because 2 + 7 = 9).

This question is the universal gateway into algorithmic interviews. It perfectly demonstrates the power of a Hash Map to trade Space for Time.

Approach 1: Brute Force ($O(N^2)$ Time, $O(1)$ Space)

The naive approach is to use a double for loop. Pick the first number, and check every other number to see if it adds up to the target.

function twoSumNaive(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

If the array has 100,000 items, this will perform 10 billion operations. It is too slow.

Approach 2: Sorting + Two Pointers ($O(N \log N)$ Time, $O(1)$ Space)

If you sort the array first, you can use the Two Pointer technique (one pointer at the start, one at the end) and squeeze inward.
However, because the problem asks you to return the original indices of the numbers, sorting the array destroys the original indices! You would have to create complex objects to track the original indices before sorting, which takes $O(N)$ extra space anyway, defeating the purpose.

Approach 3: Hash Map ($O(N)$ Time, $O(N)$ Space)

The optimal approach. We iterate through the array exactly once.
At each step, we calculate the Complement (the mathematical number we need to reach the target).
If Target is 9, and my current number is 2, my Complement is 7.

I instantly check the Hash Map: “Have I seen a 7 earlier in the array?”

• If No: I save my current number and its index in the Hash Map: { 2: index_0 }.
• If Yes: I found the pair! I return my current index, and the index of the 7 from the Hash Map.

function twoSum(nums: number[], target: number): number[] {
    // Map stores: { number_seen : its_index }
    const seenMap = new Map<number, number>();

    for (let i = 0; i < nums.length; i++) {
        const currentNumber = nums[i];
        const complement = target - currentNumber;

        // O(1) instant lookup!
        if (seenMap.has(complement)) {
            // Found it! Return the old index from the map, and the current index
            return [seenMap.get(complement)!, i];
        }

        // We haven't seen the complement. Store the current number for the future.
        seenMap.set(currentNumber, i);
    }

    return [];
}

The Evolution: 3Sum

Once you prove you understand Two Sum, interviewers will instantly pivot to 3Sum (LeetCode 15).
Problem: Find all unique triplets in the array which gives the sum of zero.

You could use a massive Hash Map for this, but dealing with duplicate triplets using Hash Maps is a nightmare.

The Golden Rule: For 3Sum, ALWAYS use Sorting + Two Pointers.

1. Sort the array ($O(N \log N)$).
2. Start a for loop pinning the first number (i).
3. For the remaining section of the array, set up Two Pointers (Left at i+1, Right at the end).
4. Run the standard Two Sum Two-Pointer squeeze to find the remaining two numbers.
   (Because the array is sorted, you can easily skip duplicate numbers with if (nums[i] === nums[i-1]) continue; to guarantee unique triplets).

Time Complexity: $O(N \log N) + O(N^2) =$ $O(N^2)$.

Interview Questions

Q: In the Two Sum Hash Map solution, what happens if the array contains duplicate numbers? (e.g., nums = [3, 3], target = 6). Will the Hash Map overwrite the first 3 with the second 3?
A: This is the brilliance of the One-Pass algorithm.
When we are at the first 3 (index 0), the complement is 3. The Map is empty, so we add {3: 0}.
When we move to the second 3 (index 1), the complement is 3. We instantly ask the Map: “Do you have a 3?” The Map says “Yes, at index 0!” We return [0, 1] instantly.
The code returns the answer before it ever has a chance to reach the seenMap.set() line, so overwriting is physically impossible.

Q: A candidate tries to solve Two Sum by doing a Two-Pass Hash Map approach: First, they loop through the entire array and put every number into the map. Then, they loop again and check for the complement. Why is this dangerous?
A: It is dangerous because of the duplicate number edge case ([3, 2, 4], target 6).
If they dump everything into the map first, the map holds {3: 0, 2: 1, 4: 2}.
During the second loop, when they look at the 3, they check if the map has a 3. The map says “Yes!” and returns index 0. The candidate returns [0, 0]. They used the exact same physical number twice to reach the target, which is an invalid answer. The One-Pass approach intrinsically protects against this.