Two Sum

Problem (restated)

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Exactly one solution exists; you may not use the same element twice.

Intuition

A nested loop is O(n²). For each value x, you need target-x. A hash map of value→index makes that lookup O(1).

Approaches

One-pass hash map

Verified

Time O(n)Space O(n)

Idea. Scan left to right. For each nums[i], if target-nums[i] was already seen, return those indices. Otherwise store nums[i]→i.

Walkthrough. nums=[2,7,11,15], target=9. See 2→store. See 7, need 2, found at 0 → [0,1].

Trade-offs. Optimal average time. Uses O(n) memory. Brute force is fine only for tiny n.

Solution

export function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]!;
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i]!, i);
  }
  throw new Error("No solution");
}

export function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]!;
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i]!, i);
  }
  throw new Error("No solution");
}

Brute force

Verified

Time O(n²)Space O(1)

Idea. Try every pair (i,j) with i < j.

Walkthrough. Compare all pairs until sum equals target.

Trade-offs. No extra memory, but too slow for large n. Good as a correctness baseline.

Solution

export function twoSumBrute(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];
    }
  }
  throw new Error("No solution");
}

export function twoSumBrute(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];
    }
  }
  throw new Error("No solution");
}

Template connection

This is the textbook hashing complement lookup from the Hashing template.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What input would break a careless off-by-one in your window/pointer logic?