Two SumEasy

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Assume exactly one valid answer exists, and you can't use the same element twice.

Examples

Input: nums = [2,7,11,15], target = 9 → Output: [0,1]

Input: nums = [3,2,4], target = 6 → Output: [1,2]

Approach

Brute force checks every pair with a nested loop — for each number, scan the rest of the array for its complement. That's correct but wasteful: by the time you're checking index j, you already know what value would complete a pair with every index before it.

The optimal approach flips the question around: instead of asking 'does some later number complete me?', ask 'have I already seen the number that completes me?' Walk the array once, and before adding the current number to a hash map, check if target minus the current number is already a key in that map. If it is, you've found your pair in one pass.

Complexity — best & worst case

Brute force — time O(n²) worst case, O(1) best case if the answer is nums[0] and nums[1]

Brute force — space O(1)

Optimal — time O(n) worst case (answer is the last pair, or scan the full array), O(1) best case (answer is the first two elements)

Optimal — space O(n) — the hash map can hold up to n-1 entries

Code

// Given an array of integers nums and an integer target, return the
// indices of the two numbers that add up to target. Assume exactly
// one valid answer, and you can't use the same element twice.

// --- Brute force: check every pair ---
function twoSumBrute(nums, target) {
  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 [];
}

// --- Optimal: one pass with a hash map ---
// For each number, check if its "complement" (target - num) was
// already seen. If so, we've found the pair — no need to look ahead.
function twoSum(nums, target) {
  const seen = new Map(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(nums[i], i);
  }
  return [];
}

// --- Example Usage ---
console.log(twoSumBrute([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([2, 7, 11, 15], 9));      // [0, 1]
console.log(twoSum([3, 2, 4], 6));           // [1, 2]
console.log(twoSum([3, 3], 6));              // [0, 1]