Matching Receipts
You went on a trip with a friend and paid for everything. Back home, your friend sends you money for exactly two of your receipts. The message only says the total: target.
You have a list of receipt amounts in the order you paid them. Which two receipts was your friend paying for?
Your task
Write findPair(amounts, target). Return the positions (indexes) of the two receipts whose amounts add up to target. You can return them in either order.
Each receipt can be used once. There is always exactly one correct pair.
findPair(amounts: int[], target: int) → int[] Any order of the returned list is accepted.
Examples
amounts = [40, 25, 75, 15] target = 100
[1, 2]
25 + 75 = 100. Those receipts sit at positions 1 and 2. No other pair works: 40 would need a 60, and 15 would need an 85.
amounts = [5, 5] target = 10
[0, 1]
Two different receipts can have the same amount. 5 + 5 = 10, using position 0 and position 1. Using position 0 twice would not count.
Constraints
- 2 ≤ amounts.length ≤ 10,000
- 1 ≤ amounts[i] ≤ 1,000,000
- Exactly one pair of different positions adds up to target.
Start with brute force
Try every pair: for each position i, check every later position j and see if amounts[i] + amounts[j] === target.
It is correct, and a fine first step. But with 10,000 receipts that is about 50 million pairs, because the number of pairs grows with n². The slow part is the inner loop: it searches the whole list for a partner every time.
Hints
0 of 4 shown- Hint 1
Pick any one receipt, say the 25 in the first example. If it is part of the answer, what must the other receipt's amount be?
- Hint 2
For each receipt
a, the partner must be exactlytarget - a. So the real question at every step is: have I already seen the amounttarget - a, and where? - Hint 3
Which data structure answers "have I seen this value, and at what position?" in one step, instead of scanning the whole list again?
- Hint 4
Walk the list once, left to right. Keep a hash map from amount to position. At each receipt, look up
target - afirst. If it is in the map, you are done. If not, storeawith its position and move on. Looking up before storing stops a receipt from pairing with itself.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The brute force searches for a partner from scratch for every receipt. The fix is to remember what you have already passed, so finding a partner is one lookup.
Trace it on [40, 25, 75, 15] with target 100:
- Position 0, amount 40. Need 60. The map is empty, so no. Store
40 → 0. - Position 1, amount 25. Need 75. Not in the map. Store
25 → 1. - Position 2, amount 75. Need 25. The map has
25 → 1. Return[1, 2].
Notice the order inside the loop: look up first, then store. If you stored first, a receipt of 50 with target 100 would find itself.
function findPair(amounts, target) {
const seen = new Map(); // amount -> position
for (let i = 0; i < amounts.length; i++) {
const need = target - amounts[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(amounts[i], i);
}
return []; // never reached: there is always a pair
}def find_pair(amounts, target):
seen = {} # amount -> position
for i, a in enumerate(amounts):
need = target - a
if need in seen:
return [seen[need], i]
seen[a] = i
return [] # never reached: there is always a pairRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.