Two Sum Interview Question

Brute force is O(n²) with nested loops. The trick: as you scan, remember what you have seen in a HashMap so you can look up the complement in O(1).

Why indices, not values? The same value can appear twice in the array, so returning the values themselves would be ambiguous — the index is what unambiguously identifies which element was used. It's also why the lookup happens before inserting the current number: checking target - n in seen first stops an element from pairing with itself.

Duplicates and "no pair found" are the two edge cases interviewers actually probe. If the same value appears twice and their indices sum to the target, the HashMap approach handles it correctly for free — the first occurrence is stored by the time the second is scanned, so the lookup succeeds without any special-casing. If no pair sums to the target, the loop finishes with nothing to return; most implementations either return an empty list / None or raise an explicit error — LeetCode's version guarantees exactly one solution exists, but a production version of this pattern (e.g. matching two transactions that net to zero) should decide and document which behavior it wants, since "guaranteed to exist" is rarely true outside a coding-interview problem statement.

Is the HashMap approach really O(n)? Strictly, that's the average-case bound — it assumes hash collisions are rare, which is the normal case with Python's/Java's default string and integer hashing. A senior-level follow-up worth having an answer for: with a pathological hash function (or a hand-crafted adversarial input designed to collide), every lookup could degrade toward O(n), making the overall algorithm O(n²) in the worst case — theoretically identical to brute force, just with extra hashing overhead on top. This is precisely why Java's HashMap treeifies long collision chains (O(n) → O(log n) worst case per bucket, covered on the HashMap resize page) rather than leaving them as plain linked lists — it caps exactly this worst case rather than eliminating the possibility of collisions entirely.

"What if we needed three numbers instead of two?" is the near-universal next question, and the HashMap trick doesn't extend directly — a triple nested loop with a HashMap lookup on the innermost is still O(n²) (one fixed index, one HashMap-assisted Two Sum on the rest), not O(n). The standard Three Sum solution instead sorts the array first (O(n log n)), then fixes one element and runs the sorted two-pointer technique on the remainder for each fixed element — O(n²) overall, but with O(1) extra space instead of a HashMap, and sorting also makes duplicate-triplet skipping trivial (skip past repeated values at each pointer), which is normally the fiddliest part of a naive HashMap-based attempt at three (or more) numbers. Interviewers rarely expect the full Three Sum solution as a follow-up to Two Sum — naming this trade-off (sort + two-pointer over nested HashMap lookups, and why) is usually enough to demonstrate the pattern generalizes.

# Two-pointer variant — only valid once the array is SORTED
def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return [lo, hi]
        elif s < target:
            lo += 1          # sum too small, need a bigger left value
        else:
            hi -= 1           # sum too big, need a smaller right value
    return None               # no pair sums to target

Keywords they're listening for: