Two Sum with a map

Direct Answer

Scan the slice once while storing each value's index in a map. For the current value x, look for target-x before storing x; this gives O(n) time and O(n) space.

Deep Dive & Architecture

Scan the slice once while storing each value's index in a map.

For the current value x, look for target-x before storing x; this gives O(n) time and O(n) space.

For every number, the only partner that can reach the target is target minus number. A map turns that lookup into constant average time.

Storing the current value before checking, which can reuse the same element.

Code Example

func twoSum(nums []int, target int) []int {
  seen := map[int]int{}
  for i, n := range nums {
    if j, ok := seen[target-n]; ok { return []int{j, i} }
    seen[n] = i
  }
  return nil
}

Common Mistakes & Pitfalls

Storing the current value before checking, which can reuse the same element.