Marauder Bot

Problem

You are handed an array of integers and a target value. Your job is to return the positions of the two entries whose values add up to that target. You can assume exactly one such pair exists, and the same element may not be used twice.

Example. For the array [2, 7, 11, 15] with a target of 9, the answer is the pair at positions 0 and 1, since 2 + 7 = 9.

Key idea

The obvious move is to try every pair of numbers, which costs O(n²). The improvement comes from reframing the question: as you look at each number x, the only value that can complete it is its complement, target - x. So rather than searching for that complement by rescanning the array, remember every number you have already passed in a hash map keyed by value.

Walk the array once. For the current number, check whether its complement is already recorded. If it is, you have found the pair and can return both indices. If it is not, store the current value together with its index and keep going. Because a hash lookup is average O(1), a single pass is enough to answer the question.

Solution

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

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]; // value that would complete the pair
    const match = seen.get(complement);
    if (match !== undefined) {
      return [match, i]; // complement was already seen earlier in the array
    }
    seen.set(nums[i], i); // record after checking, so a value can't pair with itself
  }

  return [];
}

Complexity

Time: O(n). One pass with constant-time lookups.
Space: O(n). The map may grow to hold every element.

Watch out for

Check for the complement before inserting the current element. That ordering is what stops a number from incorrectly pairing with itself.
Duplicate values are not a problem: the map is keyed by value, but you always compare against a previously stored index.

Pattern

This is the canonical "complement lookup" pattern. Whenever a problem asks for a pair that satisfies an additive constraint, a hash map that trades extra space for a faster lookup is usually the intended solution, and the same instinct scales up to three-number and k-number variants.

Two Sum