You are given a list of numbers called nums and one number called target. Find the two positions in the list whose numbers add up to target. Return those two positions.
Pick any number in the list, say 7, with a target of 9. The only number that can pair with 7 is 9 - 7 = 2. Nothing else works.
So for each number, its partner is already decided. We write it as need = target - number. The problem is really asking: "for some number, does its partner appear somewhere else in the list, and where?"
That turns a search for a pair into a search for one known value.
def twoSum(nums, target): n = len(nums) for i in range(n): for j in range(i + 1, n): # every position after i if nums[i] + nums[j] == target: return [i, j]
This makes about \frac{n^2}{2} checks. For 10,000 numbers that is 50 million checks. It passes, but slowly, and the interviewer will ask for better.
The waste in one sentence: for each i, the inner loop is just searching the list for one known value, target - nums[i], and it repeats that search from scratch every time.
Remember every number you have walked past, together with its position. Then, for the current number, compute the partner it needs and ask the memory, "have I already seen the partner, and where?"
The memory is a hash map, also called a dictionary. A hash map stores pairs of key → value and finds a key in about constant time. Here the key is a number from the list, and the value is its position.
Why store number → position, and not the other way round? Because we search by number ("is 2 in here?") and we must return a position. The thing you search by is the key. The thing you want back is the value.
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: seen = {} # (1) for i, n in enumerate(nums): # (2) need = target - n # (3) if need in seen: # (4) return [seen[need], i] # (5) seen[n] = i # (6) return [] # (7)
ts
function twoSum(nums: number[], target: number): number[] { const seen = new Map<number, number>(); // (1) for (let i = 0; i < nums.length; i++) { // (2) const need = target - nums[i]; // (3) if (seen.has(need)) { // (4) return [seen.get(need)!, i]; // (5) } seen.set(nums[i], i); // (6) } return []; // (7)}
(1) seen = {}. An empty map. It will hold "number → the position where I saw it". It starts empty because we have not walked past anything yet.
(2) for i, n in enumerate(nums).enumerate hands us two things on each turn: the position i and the number n at that position. We need both, because we look up by number and return positions.
(3) need = target - n. The partner that would complete the sum. If n is 7 and target is 9, then need is 2. This is the line that turns "search for a pair" into "look up one value".
(4) if need in seen. Have we already walked past the partner? Looking a key up in a map is constant time on average, so this replaces the whole inner loop of the brute force.
(5) return [seen[need], i]. Found it. seen[need] is the earlier position where the partner sits, and i is where we are now. The earlier position comes first, which is the order the examples use. In TypeScript, the ! after get(need) tells the compiler "I know this is not missing", which is safe because line (4) just checked.
(6) seen[n] = i. The partner is not here yet. So we remember the current number and its position, in case a later number needs it as its partner.
(7) return []. The problem promises an answer exists, so this line never runs on valid input. It is there so the function always returns a list, which TypeScript requires.
You might wonder: when we are at position i, the partner might be later in the list, and we have not seen it yet. Do we miss it?
No. Every answer is a pair of positions, one earlier and one later. When the loop reaches the earlier one, its partner is not in the map yet, so we store it and move on. When the loop later reaches the second one, its partner (the earlier one) is already in the map, so line (4) finds it. Every pair gets caught at its second position. You never need to look ahead.
Take nums = [3, 3] and target = 6, but imagine we stored first and checked second.
At position 0, we store 3 → 0.
Then we ask, "is need = 3 in the map?" Yes, at position 0.
We return [0, 0].
That uses the same position twice, which is not allowed. The same thing breaks [3, 2, 4] with target 6: position 0 would pair 3 with itself.
So we check first, then store. Then at position 0 the map is still empty, the check fails, and we store 3 → 0. At position 1, the check finds the other 3 at position 0, and we return [0, 1]. This is the same rule you met in 4.4.1: an element must never match itself.
Time. The loop runs at most n times. Each turn does one subtraction, one map lookup and at most one map insert. Each of those takes constant time on average. So the total is n turns times a constant, which is O(n).
Space. In the worst case the answer is the last two positions, and we store almost every number before finding it. So the map can hold up to n - 1 entries, which is O(n).
Two equal values, such as [3, 3]. Works because of check-before-store, as shown above.
Negative numbers, such as nums = [-3, 4, 3, 90], target = 0. The partner of −3 is 0 - (-3) = 3. The subtraction handles signs by itself.
Zero, such as [0, 4, 3, 0] with target = 0. The partner of 0 is 0. The two zeros are at different positions, so it works.
A value that repeats but is not part of the answer, such as [3, 5, 3]. The second 3 overwrites the first in the map. That is harmless. We only ever need one position for each value, and the earlier 3 already had its chance to be found.
If the list were sorted, you could put one pointer at each end and move them inward, using no extra memory. That is 4.5.2 Two Sum II.
You cannot do it here, because sorting moves the numbers to new positions, and positions are exactly what the problem asks for. To keep them, you would have to sort (value, original position) pairs. That needs O(n) extra memory anyway, and the sort costs O(n \log n) time. So you would pay more time and save no memory.
The rule: unsorted input and the answer is positions → hash map. Sorted input → two pointers.
Two Sum II. The list is sorted, so two pointers work in O(1) extra memory. 4.5.2.
3Sum. Find three numbers that add to zero. Sort, fix the first number, then run Two Sum II on the rest. 4.5.3.
Subarray Sum Equals K. Count the stretches of the list that add to k. You keep a running total as you walk, and store running totals in the map instead of single values. Then, for each running total, you look up total − k. It is the same "compute what I need, then look it up" move with a different thing in the map. This is the most useful generalisation of Two Sum.
The general lesson: when you need two things that fit a rule, fix one, work out the other from the rule, and look it up.
"Why store number → position and not position → number?" They are checking that you designed the map. You search by number, so the number is the key.
"What happens with [3, 3]?" They are checking check-before-store. If you store first, you return [0, 0].
"Can you do it in O(1) extra memory?" Only by sorting, and sorting loses the positions. Explain why that costs more than it saves.
"What if there can be many answers, and you must return all of them?" Then you cannot return on the first match. Store each value's list of positions, and be careful not to count a pair twice.
One thing to volunteer: explain why one pass is enough. Every pair is caught when the loop reaches its second position. That shows you understand the algorithm rather than remember it.
Next:4.4.4 Group Anagrams. Now the interesting part is not the map but the key you put into it.