Two Sum

Problem

You're given a list of numbers and a target value. Find the two numbers that add up to the target and return their indices. Exactly one valid pair exists, and you can't reuse the same element twice.

Your signal — what pointed here?Your skeleton — the reusable shape

Signal

Any time you need to find a pair (or a complement) satisfying a sum condition in an unsorted collection, and O(n²) isn't good enough, reach for a hash map. The trigger phrase: "find two elements such that..." with no ordering guarantee on the input.

Approach

Walk the array once. For each number, compute its complement (target - x) and check whether you've already seen it in a hash map of value → index. If you have, you've found your pair — return both indices immediately. If not, record the current number and keep going. This trades the brute force's second loop for a single O(1) lookup.

Skeleton

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

Solution

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

Complexity

O(n) time — one pass, O(1) hash map lookups. O(n) space for the hash map in the worst case (no match until the last element).

Pitfalls

Checking seen before inserting the current number — insert-then-check reuses the same element against itself when target == 2 * x.
Reaching for the sorted two-pointer trick out of habit: it costs an O(n log n) sort and loses original indices unless you carry them along. Plain hashing wins here.
Over-handling duplicate pairs — this version guarantees exactly one valid answer, so don't add bookkeeping for multiple matches unless the interviewer changes the ask.