Problem 1 · Arrays & Hashing

Two Sum

EasyClassic DSA & systems

01Problem

Given an integer array nums and a target, return the indices of the two distinct elements that sum to target. Exactly one solution exists.

02Key insight

Trade space for time: a single pass with a value->index hash map turns the O(n^2) pair search into O(n) complement lookups. Check before inserting so an element never pairs with itself.

03Solution

solution.pypython8 lines

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        j = seen.get(target - x)
        if j is not None:
            return [j, i]
        seen[x] = i
    return []

Try it first.

TimeO(n)

SpaceO(n)

tests.py · 4 passing

tests.pypython4 lines

assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([3, 3], 6) == [0, 1]
assert two_sum([-1, -2, -3, -4, -5], -8) == [2, 4]
assert two_sum([1, 2], 7) == []

04Staff-level follow-up

What if the input is sorted or too large for memory? Sorted: two pointers in O(1) space; huge: external sort then two pointers, or hash-partition by value bucket so complements land in paired partitions.