You're buying two gifts from a shop's price list and want to spend your budget exactly. Write a function that takes a list of whole-number prices and a budget, and returns the positions [i, j] (with i < j) of two different items whose prices add up to budget.
If more than one pair works, return the one you'd spot first reading the list left to right: the pair with the smallest j, and for that j, the smallest i. If no pair works, return an empty list.
text
1gift_pair([12, 30, 7, 18, 25], 37) -> [1, 2]
2gift_pair([5, 5, 10], 10) -> [0, 1]
3gift_pair([4, 9, 2], 8) -> []
Example 1
12
0
30
1
7
2
18
3
25
4
prices[1] + prices[2] = 30 + 7 = 37, so the answer is [1, 2].
In the first example, 30 + 7 = 37. In the second, two different items can have the same price. In the third, 4 + 4 would mean buying the same item twice, so there's no answer.
Write gift_pair(prices, budget) in Python or giftPair(prices, budget) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 20 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Start with the obvious answer
Try every pair: for each j, look at every i before it and check whether prices[i] + prices[j] == budget. Checking j in order, and i in order inside it, gives exactly the pair the problem asks for. That's correct, but it's O(n²): a list of 100,000 prices means about 5 billion checks.
Step 2
Ask what you're really looking for
When you're standing on item j, you don't need to check every earlier item. You need to know one thing: has the price budget - prices[j] appeared before, and where? That's a lookup, not a search.
Step 3
Use a hash map for the lookup
Keep a map from each price you've seen to its index. Lookups take O(1) on average, so each item costs constant time instead of a scan.
Step by step1 / 3
j
12
0
30
1
7
2
18
3
25
4
keyindexempty
j = 0: need 37 − 12 = 25. Not in the map, so store 12 → 0.
Step 4
Keep the earliest index
If a price appears twice, keep the index of its first appearance (only add it if it isn't already in the map). That way, when you find a match, i is the smallest possible. And because you check before you add, an item is never paired with itself.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Walk through the list once. For each price, compute what you'd need to hit the budget. If that amount is already in the map, you've found the earliest pair ending here, so return it. Otherwise, remember this price's index (only the first time you see it) and move on.
python
1def gift_pair(prices, budget):
2 first_seen = {} # price -> index of its first appearance
↑price -> where we first saw it
3 for j, price in enumerate(prices):
4 need = budget - price
↑the price that would complete the pair
5 if need in first_seen:
↑O(1) lookup, no inner loop!
6 return [first_seen[need], j]
7 if price not in first_seen:
↑keep the FIRST index only
8 first_seen[price] = j
9 return []
javascript
1function giftPair(prices, budget) {
2 const firstSeen = new Map() // price -> index of its first appearance
↑price -> where we first saw it
3 for (let j = 0; j < prices.length; j++) {
4 const need = budget - prices[j]
↑the price that would complete the pair
5 if (firstSeen.has(need)) return [firstSeen.get(need), j]
↑O(1) lookup, no inner loop!
6 if (!firstSeen.has(prices[j])) firstSeen.set(prices[j], j)
↑keep the FIRST index only
7 }
8 return []
9}
Complexity
TimeO(n)SpaceO(n)
O(n) time, since each item is looked up and stored once, and O(n) extra space for the map.
What we learned
"Have I seen X before?" is a hash map question. It turns an O(n) search into an O(1) lookup.
Look up first, then store. That order stops an item from pairing with itself.
When the problem says which answer to return, check that your loop order and what you keep in the map match it.