Two Sum | Engineering Interview Kit

Concept

LeetCode #1.
Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] (Because nums[0] + nums[1] == 9).

This is the most famous algorithm problem in existence. Every software engineer must know how to solve this instantly.

The Brute Force Approach ( $O(N^2)$ )

You could use nested for loops to check every single possible combination of two numbers.

function twoSumBruteForce(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 [];
}

This is $O(N^2)$ time. In an interview, you should mention this solution in exactly 5 seconds, and immediately say: “But I can optimize this to $O(N)$ using a Hash Map.”

The Optimal Approach ( $O(N)$ )

Instead of checking every combination, we can use algebra.
If we are looking at the number 2, and the target is 9, what number do we need to find?
9 - 2 = 7. We need a 7!

We can create a Hash Map (Map<number, number>) where the Key is the number we have seen, and the Value is the index where we saw it.

As we iterate through the array:

Calculate the complement (Target - Current Number).
Check the Hash Map: “Have I already seen the complement earlier in the array?”
If YES: We found the pair! Return the index from the Hash Map, and our current index.
If NO: Add our current number and index into the Hash Map, and move to the next number.

Implementation

// Time Complexity: O(N) (One single pass)
// Space Complexity: O(N) (The Hash Map)

function twoSum(nums: number[], target: number): number[] {
    // Map tracks: { numberInArray : index }
    const seen = new Map<number, number>();

    for (let i = 0; i < nums.length; i++) {
        const currentNum = nums[i];
        
        // 1. What number do we need to hit the target?
        const complement = target - currentNum;

        // 2. Did we see that number earlier?
        if (seen.has(complement)) {
            // WE FOUND IT!
            return [seen.get(complement)!, i];
        }

        // 3. We didn't find it. Save the current number for future lookups.
        seen.set(currentNum, i);
    }

    return []; // Should never hit if the problem guarantees a solution
}

Two Sum II (Sorted Array)

LeetCode #167. Problem: What if the input array is already sorted? You cannot use $O(N)$ extra space.

If the array is sorted, you cannot use the Hash Map approach because it takes $O(N)$ space. Instead, you use the Two Pointers technique!

Place a pointer at left = 0 and right = nums.length - 1.
Add the two numbers together.
If the sum is exactly the target, you win!
If the sum is TOO SMALL, you must increase the sum. How? Move the left pointer to the right! (Since the array is sorted, moving right guarantees a larger number).
If the sum is TOO BIG, you must decrease the sum. Move the right pointer to the left!

// Time Complexity: O(N)
// Space Complexity: O(1)

function twoSumSorted(numbers: number[], target: number): number[] {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        const currentSum = numbers[left] + numbers[right];

        if (currentSum === target) {
            // LeetCode #167 asks for 1-indexed output!
            return [left + 1, right + 1]; 
        } else if (currentSum < target) {
            left++; // Sum too small, slide left pointer up
        } else {
            right--; // Sum too big, slide right pointer down
        }
    }

    return [];
}

Interview Questions

Q: In standard Two Sum, what happens if there are duplicate numbers in the array? (e.g., [3, 3], target 6)
A: The Hash Map approach handles duplicates perfectly!

Loop 1: Sees the first 3. Complement is 3. Not in map. Adds {3: 0}.
Loop 2: Sees the second 3. Complement is 3. IS IT IN THE MAP? Yes! It instantly returns [0, 1]. The Hash Map doesn’t even need to overwrite the duplicate key because it finds the solution before it gets to the .set() line.

Q: Can you use a standard JavaScript object {} instead of new Map()?
A: Yes, const seen = {} works and is extremely common. However, Map is strictly better in interviews for two reasons:

Map guarantees $O(1)$ lookup time, whereas standard Objects in V8 can theoretically degrade into “dictionary mode” which is slightly slower.
Map allows negative numbers as literal numeric keys. If you use {}, JavaScript implicitly casts all keys to Strings (seen["-5"] = 0), which incurs minor string conversion overhead.