Loading page…
Practice problem · easy
Kestrel Pay lists every entry of a merchant's settlement as a signed amount in minor units. A payment is positive and a refund is negative.
A merchant disputes a net movement of total. Support believes it comes from exactly two entries in the list, and it needs their positions, so that it can show both to the merchant.
Write refund_pair(amounts, total).
amounts[i] is the i-th entry. Positive values are payments and negative values are refunds.i < j with amounts[i] + amounts[j] == total.j. For that j, return the smallest i.[i, j], or [-1, -1] when no two entries make the total.Input: amounts = [120, -35, 80, 45, -60, 95], total = 60
Output: [0, 4]Each entry looks for the partner total - amount among the earlier entries.
| Position | Amount | Partner needed | In the map? | Map after |
|---|---|---|---|---|
| 0 | 120 | -60 | no | 120 at 0 |
| 1 | -35 | 95 | no | adds -35 at 1 |
| 2 | 80 | -20 | no | adds 80 at 2 |
| 3 | 45 | 15 | no | adds 45 at 3 |
| 4 | -60 | 120 | yes, at position 0 | pair found |
The pair -35 and 95 also makes 60, but its second position is 5, so the pair at positions 0 and 4 comes first.
Input: amounts = [25], total = 50
Output: [-1, -1]One entry cannot pair with itself.
Input: amounts = [-7, 3, 7], total = 0
Output: [0, 2]The refund -7 cancels the payment 7.
1 ≤ amounts.length ≤ 100,000 (entries in one settlement)-10^9 ≤ amounts[i] ≤ 10^9 (minor units; refunds are negative)-10^9 ≤ total ≤ 10^9Trying every pair costs about n × n / 2 checks. At n = 100,000 that is about 5 × 10^9, far over the budget of about 10^8 simple operations a second. A hash map finds a partner in one step on average, so one pass makes about n steps.
Read the values too. An amount and the total are at most 10^9, so total - amount is at most 2 × 10^9 in size. That still fits in a 32-bit int, which holds up to about 2.1 × 10^9.
refund_pair · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.