Two Sum

Problem Summary

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Intuition

The brute force approach checks every pair, giving O(n²) time. We can do better by recognizing that for each number, we need to find its complement (target - num). A hash map allows O(1) lookups, letting us solve the problem in a single pass.

As we iterate, we store each number and its index. Before storing, we check if the complement already exists in our map. If it does, we've found our answer.

Approach

1. Initialize an empty hash map seen
2. Iterate through the array with index and value
3. Compute complement = target - num
4. If complement exists in the map, return both indices
5. Otherwise, store num → index in the map

Complexity

Code

function twoSum(nums: number[], target: number): number[] {

    const map = new Map<number, number>();

    for (let i = 0; i < nums.length; i++) {

        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
}