Skip to content
GKgkml.dev
← Problem set
#1EasyArrays & hashing

Two Sum

The tell: Find a pair summing to a target, and the array is unsorted with indices required.

How you get there

  1. 1The brute force asks 'is target - x anywhere else?' once per element, rescanning every time.
  2. 2Store what you have already seen in a dict mapping value to index.
  3. 3For each x, the complement is a single O(1) lookup — so one pass answers it.

Solution

Python
def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i          # store after checking, so x cannot pair with itself
    return []
Time
O(n)
Space
O(n)

What goes wrong

Storing x before checking the complement lets an element match itself when target is 2*x.

Test yourself on DSANext: Valid Sudoku →