Two Sum

Return the indices of two numbers that add to the target.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Two Sum: Check each complement before saving the current value.

Input and goalReturn the indices of two numbers that add to the target.

Initialize the lookupBefore index 0, seen is empty; the only retained state will map each scanned value to its index.

current i=030214273

examplenums = [3, 2, 4, 7], target = 6target6mapLabelseen: value -> index

seen: value -> indexempty

Recognize it

The prompt asks for two positions whose values satisfy a target sum, so each current value determines one exact complement that can be looked up.

Keep true

Before processing index i, seen contains exactly the useful values from indices below i; therefore a hit is an earlier, distinct element.

Reuse it

When a current item determines one exact missing partner, store only prior facts needed to recognize that partner; this transfers to complement, difference, and prefix-sum lookup problems.

Pattern: Hash map.

Simple idea: For each number, calculate the number it needs. If that needed number was seen earlier, the pair is complete. Check first, then save the current number. This avoids using the same item twice.

def two_sum(nums: list[int], target: int) -> list[int]:
   seen: dict[int, int] = {}
   for index, num in enumerate(nums):
      needed = target - num
      if needed in seen:
         return [seen[needed], index]
      seen[num] = index
   return []

Cost: $O(n)$ time and $O(n)$ space.