---
title: "Two Sum (LeetCode #1)"
description: "Two indices whose values sum to target — one-pass hash map walkthrough"
source: https://vizlearn.app/algorithms/leetcode/two-sum
---

# Two Sum (LeetCode #1)

Two Sum — LeetCode problem #1 — asks for the two indices in an array `nums` whose values add up to a `target`. The one-pass hash-map solution walks the array once, asking at each element whether its complement has already been seen, and cuts the time complexity from the brute-force O(n²) to O(n).

Think of a doorman with a guest list. As each guest arrives, he doesn't run back through the whole party looking for their partner — he checks the list first: "is the person who would complete this pair already inside?" If yes, done. If no, he writes the newcomer down and waits for the next arrival. The list is the hash map; the check-then-write order is the whole algorithm.

## How Two Sum Works

Walk the array left to right, maintaining a dictionary `seen` that maps each value to its index. At position `i`, compute `complement = target - nums[i]` — the partner value this element needs. Check whether the complement is already in `seen`; if it is, return `[seen[complement], i]`, earlier index first. Only after the check fails do you insert the current element: `seen[nums[i]] = i`.

That ordering — check the list *before* writing yourself onto it — is the load-bearing detail. When `nums[i]` happens to equal `target / 2`, a same-iteration lookup would find the element you just inserted and pair it with itself, which the problem forbids. Because the check runs against the map as it stood *before* this iteration, an element can never be its own partner.

The naive alternative tests every pair `(i, j)` with `j > i` in a double loop. No memory, no dictionary — just n(n−1)/2 candidate pairs, O(n²). Both solutions are animated here: the **Approach** toggle in the Inputs panel switches between **Hash map** (the default) and **Brute force** on the same input.

## Two Sum Step by Step

The default input is `nums = [2, 7, 11, 15]` with `target = 18`, hash-map approach:

1. **`i = 0`, `nums[i] = 2`.** `complement = 18 − 2 = 16`. Is 16 in `seen`? No — the map is empty. Insert `seen[2] = 0`.
2. **`i = 1`, `nums[i] = 7`.** `complement = 18 − 7 = 11`. Not in `seen`. Insert `seen[7] = 1`. The map is now `{2: 0, 7: 1}`.
3. **`i = 2`, `nums[i] = 11`.** `complement = 18 − 11 = 7`. Is 7 in `seen`? Yes — at index 1. Return `[1, 2]`. The doorman never even glances at the 15.

Flip the toggle to brute force and the same input takes four pair checks: `2 + 7 = 9`, `2 + 11 = 13`, `2 + 15 = 17`, then `7 + 11 = 18` — return `[1, 2]`. Same answer, but the running `checks` counter in the header is the number to watch: it grows with the *square* of the input, while the hash map's pass stays linear.

In the visualization, the array sits on the right and `seen` builds up as a two-column "value | index" panel on the left — the guest list, made literal. Each iteration runs four beats: the active cell glows, the complement is computed, the dictionary is probed, and the element either matches (the dict row and the active cell turn green together — they are the pair) or is written into `seen` — a new row, or an overwrite of its row when the value repeats. In brute-force mode the panel disappears entirely; that absence *is* the difference between the two approaches.

## Time and Space Complexity

| | Brute force | Hash map |
|---|---|---|
| Best case | O(1) — first pair matches | O(1) — pair at indices 0, 1 |
| Worst case | O(n²) | O(n) expected (O(1) hash lookups) |
| Space | O(1) | O(n) |

The space buys the speed: the hash map spends O(n) memory to make "have I seen your partner?" a constant-time question instead of a rescan. At the default's tiny `n = 4` the two finish in a comparable number of beats — grow the input and watch the `checks` counter pull away while the hash map's work grows only linearly.

## Edge Cases

The player accepts 3–8 values in the range 1–99, so a couple of these are worth working on paper.

- **No solution.** LeetCode guarantees exactly one answer, but the displayed code simply falls off the end of the loop (returning `None` in Python). The animation surfaces this honestly with an explicit "no solution" beat rather than crashing; real code should handle it explicitly.
- **The pair is two equal values** — say `nums = [3, 3, 4]`, `target = 6`. At `i = 1`, the complement 3 is already in `seen` from index 0, so the result is `[0, 1]`. This works *only* because of check-before-insert.
- **Duplicates not in the answer.** A repeated value overwrites its row in the map — safe, because the earlier index's own complement check has already run by the time it gets overwritten.
- **Negatives and zero** need no special handling — a hash map keys on any integer — though the player's input range keeps them off the canvas.

## Common Mistakes

- **Insert before check.** The most common bug. It looks symmetric, but it lets `target / 2` match the element you just wrote down — the doorman pairing a guest with their own name tag.
- **Returning values instead of indices.** The problem wants positions. The map must store indices as its values, not the numbers themselves.
- **Sorting first to use two pointers.** Sorting destroys the original indices; recovering them means carrying each value's position along, which is more bookkeeping than the hash map needed in the first place.
- **Using a set instead of a map.** A set answers "is this value present?" but not "at which index?" — and the index is the output.