Two prices that use up a credit exactly
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A customer has a store credit and a list of item prices. They want two different items whose prices add up to the credit exactly.
Return the positions [i, j], with i < j, of the pair whose second item comes earliest in the list; if several pairs share that second item, use the earliest first item. Return [] if no pair adds up exactly.
- 0 ≤ prices.length ≤ 200,000
- 0 ≤ prices[i] ≤ 10⁹
- 0 ≤ credit ≤ 2 × 10⁹
Examples
pairForCredit([8, 3, 5, 2, 6], 8)returns[1, 2]3 + 5. The pair 2 + 6 also adds up, but it finishes later.pairForCredit([4, 4], 8)returns[0, 1]pairForCredit([1, 2, 3], 7)returns[]
Hints
Hint 1 of 2
For each price, the partner you need is credit - price. Has it already appeared?
Hint 2 of 2
Keep a map from price to the first position it appeared at. Check for the partner before adding the current price, so an item never pairs with itself.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Checking every pair is quadratic. Instead, walk the prices once: at position j, the only partner that works is credit - prices[j], so the question is whether that value appeared earlier, and where.
The tie rule says to prefer the earliest first item, so the map stores the first position of each price and never overwrites it. Storing the latest position is the most common slip.
Look up the partner before adding the current price. Otherwise a price of exactly half the credit finds itself and returns [j, j]: one item bought twice.
function pairForCredit(prices, credit) {
const first = new Map();
for (let j = 0; j < prices.length; j++) {
const need = credit - prices[j];
if (first.has(need)) return [first.get(need), j];
if (!first.has(prices[j])) first.set(prices[j], j);
}
return [];
}Complexity. O(n) time and O(n) space.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.