Two prices that use up a credit exactly

MediumAbout 20 minProblem 3 of 3 in Hash mapsDraft

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

  1. pairForCredit([8, 3, 5, 2, 6], 8)returns [1, 2]3 + 5. The pair 2 + 6 also adds up, but it finishes later.
  2. pairForCredit([4, 4], 8)returns [0, 1]
  3. 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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open