TechPrep
Arrays and stringsReadLabPracticeCheck

Hash maps and counting

Trade memory for time: remember what you have seen so the inner loop becomes a lookup.

Two Sum. Given an array nums and a target, return the indices of the two numbers that add up to target. Exactly one answer exists; do not use the same element twice.

Signals that point here

The idea

The brute force checks every pair, O(n²). But for each x the partner is fully determined: target - x. A hash map of values already seen answers "have I met the partner?" in O(1) on average.

The invariant: when you stand at index i, seen holds every value to the left of i. Checking before inserting is what stops an element pairing with itself.

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

Complexity

O(n) time on average, O(n) extra space. Worst-case hashing is O(n) per operation, which is worth one sentence if the interviewer asks about adversarial input.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: two_sum([3, 8, 4, 11, 6], 10)

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Return all unique pairs that sum to target, with duplicates in the input.
  2. Find the length of the longest run of consecutive integers in an unsorted array in O(n).
  3. Given a list of words, group the anagrams together.

Check yourself

Why check before inserting?

So an element cannot pair with itself; seen must hold only indices strictly to the left.

What does the hash map buy, and what does it cost?

Turns the inner search from O(n) into average O(1), for O(n) extra memory.

Saved in this browser.