ASAPUtils
This page is the reference template. Every other problem write-up follows exactly this shape — see
docs/dsa/07-content-templates.md. Copy it, don’t reinvent it.
The signal
Find two elements satisfying a relation · the array is unsorted · return indices.
Unsorted rules out two pointers, because there’s no order to exploit and sorting would destroy the indices you have to return. What’s left is: for each element, can I look up the thing I need in O(1)? That’s a hash map. The phrase “have I seen X already?” is the signal, and it shows up constantly.
Approach ladder
1. Brute force — O(n²)
Check every pair with a double loop. Correct, and for n ≤ 10⁴ it even passes. State it out
loud in an interview, then immediately ask the next question:
2. What is the brute force wasting?
For each i, the inner loop re-scans elements it has already visited on previous outer
iterations. That’s the waste. We’re recomputing “is value X somewhere in this array?” over and
over — and re-scanning for something you already saw is exactly the signal for a hash map.
3. The insight
We don’t need to search for a pair. Standing at index i, there is only one number that
completes it: target - nums[i]. So the question collapses from “which two elements?” to
“have I already walked past target - nums[i]?” — one O(1) lookup instead of a scan.
4. Optimal — O(n), one pass
Walk once. At each element, check the map for the complement. If it’s there, done. If not, record the current value and move on. Every pair gets completed by its later element, so one pass is genuinely enough — you never need to look forward.
Walkthrough
On nums = [2, 7, 11, 15], target = 9:
| i | nums[i] | need | map before | action |
|---|---|---|---|---|
| 0 | 2 | 7 | {} | 7 not seen → store 2 → 0 |
| 1 | 7 | 2 | {2: 0} | 2 is at index 0 → return [0, 1] |
Run it on your own input with the visualizer below.
Complexity
- Time O(n) — one pass, and each map operation is O(1) on average.
- Space O(n) — the map holds up to
nentries in the worst case.
Worth saying out loud: this is a classic time–space trade. You bought an O(n) speedup by spending O(n) memory. Being able to name the trade is what shows you understand the solution rather than remember it.
Traps
- Returning values instead of indices. Read the return type twice.
- Pairing an element with itself. Check the map before inserting the current value.
- Duplicates.
nums = [3, 3],target = 6works fine here, because the second 3 finds the first one already in the map. But note that storing value → index means a later duplicate overwrites an earlier one; that’s harmless here and a real bug in problems that need all pairs. - Assuming the array is sorted. It isn’t. That’s Two Sum II, which is a different problem with a different answer (two pointers, O(1) space).
Blank re-solve prompt
Given an unsorted array and a target, return the indices of the two numbers that add to it, in a single pass. No hints, no looking above.
Do this from an empty file, three days from now. That re-solve is what turns “solved” into “mastered” — the first pass doesn’t count.