Two Sum

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.

You may assume each input has exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Why:    nums[0] + nums[1] = 2 + 7 = 9

Input:  nums = [3, 2, 4], target = 6
Output: [1, 2]

Intuition

Start with the obvious idea: try every pair. Take 2, check it against 7, 11, 15. Take 7, check it against 11, 15. That works, but for an array of 10,000 numbers it means about 50 million comparisons.

Here is the shift in thinking that makes it fast:

So the question changes from "which of the remaining numbers pairs with me?" (slow, requires scanning) to "have I already seen the number 7?" (fast, if you kept notes).

A hash map is the notebook. Writing down number → index costs O(1), and asking "is 7 in my notes?" also costs O(1).

Real-world analogy

Imagine you are matching socks from a laundry pile. The slow way is to pick one sock and compare it against every other sock. The fast way: lay each sock on a table in a labelled spot as you pull it out. When you pull out a red sock, you don't search — you look straight at the "red" spot to see if its partner is already there.

Approach

Watch it run

Solution

def two_sum(nums: list[int], target: int) -> list[int]:
    """Return the indices of the two numbers that add up to target."""
    seen: dict[int, int] = {}  # number -> index it was found at

    for i, num in enumerate(nums):
        complement = target - num

        # Check before inserting so an element can't pair with itself.
        if complement in seen:
            return [seen[complement], i]

        seen[num] = i

    return []  # unreachable when a solution is guaranteed

Complexity Analysis

• Time — one pass over n elements, and each hash-map read or write is O(1) on average. Compare with the brute-force O(n²): at n = 10,000 that is 10,000 steps instead of ~50,000,000.
• Space — in the worst case (the pair is the last two elements) the map holds nearly every number.

Edge Cases

Related Problems

• Contains Duplicate — the same "have I seen this before?" trick, with a set instead of a map
• Group Anagrams — a hash map keyed by a computed signature
• Container With Most Water — when the array is sorted-ish, two pointers beat a map