What to Store in the Map

What is this?

The hash table itself never changes — it is always the same instant-lookup box. What makes a problem click is choosing the right "ticket" to store. As you walk through the data, you ask what fact about the past you need to look up instantly, and you store exactly that. Pick the clever key and a slow, compare-everything-to-everything approach shrinks to a single pass.

flowchart TD A["Read the next element"] --> B["Define its partner"] B --> C["Ask the map for the partner"] C --> D["Found so use it for the answer"] C --> E["Record this element as a key"] E --> A

💡 Fun fact: The "store running totals and look up the difference" idea behind Subarray Sum has a deep cousin in math called prefix sums, used as far back as 19th-century actuarial tables to total columns of figures quickly. The same move turns a question about any range into a single subtraction.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Every problem here uses the same hash map — what changes is the clever choice of key and value. Store the right thing and an O(n²) scan becomes a single O(n) pass. The art is asking: "as I walk the data, what fact about the past do I need in O(1) — and what key unlocks it?"

The move

The move: for each element, answer += what the map already knows about my partner (an O(1) question), then record my own key to value (update the map)

The trick is defining "partner" and the key:

Two Sum → partner = target - x; store value → index.
Subarray Sum Equals K → partner = a previous prefix sum s - k; store prefix-sum → count (seed {0:1}).
Pairs of Songs Divisible by 60 → partner = (60 - r) % 60; store remainder → count.

The three problems

What to store in the map: Two Sum stores value to index, Subarray Sum = K stores prefix-sum to count, Pairs divisible by 60 stores remainder to count

Problem	Key → value	Partner you look up
Two Sum	value → index	`target - x`
Subarray Sum Equals K	prefix-sum → frequency	`running_sum - k` (seed `{0:1}`)
Pairs of Songs ÷ 60	remainder mod 60 → count	`(60 - r) % 60` (watch r=0, r=30)

Notice the escalation: Two Sum stores the raw value; Subarray Sum stores a derived quantity (a prefix sum) and its frequency; Pairs stores a transformed key (a remainder). Same machine, smarter keys.

The pattern

"Count-as-you-go" works because the map only ever holds the past, so a pair/window is counted exactly once (you ask about the partner before recording yourself). The hard part is never the map — it's the algebra that turns the condition ("sum to target", "sum divisible by k") into a lookup key.

⚠️ Two recurring traps: seed the map when the empty prefix counts ({0:1} in Subarray Sum), and count before insert to avoid pairing an element with itself.

📓 Draw it yourself

Complement lookup. For Two Sum, draw the map filling and circle when target - x is already present.
Prefix-sum counts. For Subarray Sum = K, draw the running sum and the prefix→count map (with {0:1}); mark where s - k has been seen before.

Snap photos and embed them with the /host-diagrams skill.

Key takeaways

The map is fixed; the key/value is the puzzle — value→index, prefix-sum→count, remainder→count.
Turn the condition into a lookup key (complement, s-k, (k-r)%k) so each step is O(1).
Count-as-you-go keeps the map = past, so each pair/window is counted once.
Seed and order matter — {0:1} for empty prefix; ask before you insert.
Why interviewers love it: it separates "I know hash maps" from "I know what to put in one."

Order: Two Sum → Subarray Sum Equals K → Pairs of Songs With Total Durations Divisible by 60.

Foundations