Two Sum
The classic warm-up: find the two numbers that add up to a target. Brute force is O(n²) — a hash map gets you to one pass, O(n). Solve it in Python or TypeScript, in your browser.
The problem
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not use the same element twice. Return the indices in increasing order.
nums = [2, 7, 11, 15], target = 9[0, 1]nums = [3, 2, 4], target = 6[1, 2]nums = [3, 3], target = 6[0, 1]- 2 ≤ nums.length ≤ 10⁴
- Exactly one valid answer exists.
- Aim for O(n) time — one pass with a hash map beats the O(n²) double loop.
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.
Implement two_sum(nums, target): return the two indices (increasing order) whose values sum to target. One pass with a hash map of value → index gets you O(n).
- Brute force checks every pair — O(n²). The trick is to remember what you have already seen.
- Walk the array once, keeping a map of
value → index. - At each number
x, the partner you need istarget - x. If it is already in the map, you are done. - Store
x → its indexonly after checking, so you never pair an element with itself.
Approach, complexity & discussion — open after you solve
The approach
Brute force checks every pair — O(n²). The one-pass trick trades space for time: walk the array once, and for each value x ask a hash map “have I already seen target − x?” If yes, you have your pair; if no, record x → its index and move on. Because you check before inserting, you never pair an element with itself.
Complexity
Time O(n), space O(n) for the hash map. (The brute-force nested loop is O(n²) time but O(1) space — the classic space-for-time trade.)
Common mistakes
- Pairing an element with itself — check for the complement before inserting the current value.
- Assuming the array is sorted (that is the two-pointer solution) — the hash-map approach needs no ordering.
- Returning the values instead of the indices the problem asks for.
- Rebuilding the “seen” map each iteration instead of carrying it through the single pass.
Where this shows up
“Remember what you’ve seen in a hash map, then answer in O(1)” is one of the most reused patterns in all of engineering — deduplication, hash joins, caches, detecting repeats in a stream, and reconciliation all run on it. Two-sum is the smallest possible instance of trading memory for a linear-time lookup.
Explore the topic
See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.