Two Sum

Interview Prep

Warm-upArrays & Hashingarrayshashmap

The problem

Given an array of integers nums and a target sum, return the indices of the two numbers that add up to the target. Each input has exactly one solution, and you can return the indices in any order.

Pattern: complementary lookup with a hashmap

The trick is to stop thinking "find both numbers" and start thinking "find one and check whether its complement is already in our memory." A hashmap of value → index turns the second lookup into O(1).

Recognize this pattern any time the question is "find a pair (or triple) summing to X" or "have I seen this exact value before." Hashmap-as-memory is the first thing to reach for.

Brute force

Two nested loops — try every pair. Quadratic time, constant extra space. It's a useful starting point because it gives the interviewer something to shoot down before you fire the optimal solution.

def two_sum(nums: list[int], target: int) -> list[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Time O(n²). Space O(1). For n = 10⁵ this is already past most online-judge time limits.

Optimal

Walk the array once. At each index i, compute what the complement would be (target - nums[i]). If we've seen that complement before, we have our pair. If not, remember the current value for someone later to find.

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}          # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    return []

Time O(n) — one pass. Space O(n) — the hashmap.

Walkthrough

nums = [2, 7, 11, 15], target = 9

i = 0  x = 2   complement = 7   seen = {}            → not found, store 2:0
i = 1  x = 7   complement = 2   seen = {2: 0}        → hit, return [0, 1]

Read the loop in your head: at each step ask "is the complement already there?" before remembering the current value. Order matters — storing first would let an element pair with itself.

Edge cases

Duplicates that sum to the target. nums = [3, 3], target = 6. The first 3 goes in the hashmap; the second 3 finds it as its own complement. Returns [0, 1].
No valid pair. The problem guarantees one exists in interviews, but a defensive return is still good. The empty list is a fine sentinel.
Negative numbers and zero. The hashmap handles them transparently; nothing about the algorithm assumes positivity.

Two Sum II — Sorted Array. Sorted inputs unlock an O(1)-space two-pointer sweep. Different pattern, same problem shape.
Three Sum. Sort first, then for each anchor run a two-pointer scan over the rest. Builds directly on this pattern.
4 Sum. Two anchors plus the same two-pointer inner. The pattern keeps composing.