Two Sum

Problem

Given an array of integers nums and an integer target, return the indices of the two numbers whose sum is equal to target.

You may assume there is exactly one valid answer, and you cannot use the same element twice.

Mind Map

• Need two values that combine to target.
• For each number, calculate the missing value: target - current.
• If the missing value was already seen, the answer is ready.
• Otherwise, store the current number with its index for future checks.

Brute Force Approach

Compare every pair of numbers and return the pair whose sum matches the target. This is simple, but it repeats work because every number is checked against many other numbers.

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

Time complexity: O(n^2)
Space complexity: O(1)

Optimized Approach

Use a hash map to remember numbers already visited. For every current number, ask one question: "Have I already seen the value needed to complete the sum?"

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

  for (let index = 0; index < nums.length; index++) {
    const current = nums[index];
    const required = target - current;

    if (seen.has(required)) {
      return [seen.get(required)!, index];
    }

    seen.set(current, index);
  }

  return [];
}

Time complexity: O(n)
Space complexity: O(n)

Walkthrough

For nums = [2, 7, 11, 15] and target = 9:

1. At 2, required value is 7. Store 2 -> 0.
2. At 7, required value is 2. It exists in the map.
3. Return [0, 1].

Edge Cases

• Duplicate values, such as [3, 3] with target 6.
• Negative numbers, such as [-1, -2, -3].
• A valid answer appearing near the end of the array.