#1 Two Sum

Problem Statement

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, but we can do better. As we iterate through the array, we can store each number's index in a hash map. For each new number, we check if its complement (target - current number) already exists in the map.

The key insight is that lookup in a hash map is $O(1)$, turning our nested loop into a single pass.

Approach

1. Create an empty hash map to store values and their indices.
2. Iterate through the array with index i.
3. Compute complement = target - nums[i].
4. If the complement exists in the map, return [map[complement], i].
5. Otherwise, store nums[i]: i in the map.

Solution

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);
  }

  throw new Error("No solution found");
}

Complexity Analysis