Largest charge with a matching refund

Scenario

A banking app shows a card statement. Charges are positive amounts and refunds are negative amounts, in minor units.

The app wants a badge for the biggest charge that was refunded in full. That means a charge of k and a refund of exactly -k both appear on the statement.

You are asked to find that amount.

Your task

Write largest_matched_amount(amounts).

amounts[i] is one line of the statement. A positive value is a charge. A negative value is a refund. No line is 0.
Return the largest positive k such that both k and -k appear in amounts.
Return -1 if there is no such k.
The statement may repeat an amount. One refund is enough to match a charge of the same size.

Examples

Example 1 (traced)#

text2 lines

Input:  amounts = [900, -1500, 350, -350, -90, 40, 1000, -1200]
Output: 350

Sort the amounts: [-1500, -1200, -350, -90, 40, 350, 900, 1000]. Pointer lo starts at the most negative refund and hi at the largest charge. At each step compare their sizes.

Equal sizes are a match. Otherwise the larger size has no partner and its pointer moves in.

lo	hi	Refund at lo	Charge at hi	Sizes	Move
0	7	-1500	1000	1500 and 1000	the refund is larger: lo becomes 1
1	7	-1200	1000	1200 and 1000	the refund is larger: lo becomes 2
2	7	-350	1000	350 and 1000	the charge is larger: hi becomes 6
2	6	-350	900	350 and 900	the charge is larger: hi becomes 5
2	5	-350	350	350 and 350	equal sizes: return 350

Example 2#

text2 lines

Input:  amounts = [1000, 250, -300]
Output: -1

There is a refund, but no charge of 300. There is no match.

Example 3#

text2 lines

Input:  amounts = [3, -3, 8, -8, 8]
Output: 8

Both 3 and 8 are matched. The largest is 8. The extra charge of 8 changes nothing.

Constraints

1 ≤ amounts.length ≤ 100,000 (lines on one statement)
-1,000,000,000 ≤ amounts[i] ≤ 1,000,000,000, and amounts[i] ≠ 0 (minor units)

What does n ≤ 10^5 tell you?

Checking every charge against every line costs about n × n ÷ 2 steps in the worst case. At n = 100,000 that is about 5 × 10^9, roughly 50 seconds at 10^8 operations a second. Sorting costs about n × log n, under 2 million steps, and the walk after it makes at most 100,000 steps.

The answer is at most 1,000,000,000, which fits in a 32-bit integer.

Scenario

A banking app shows a card statement. Charges are positive amounts and refunds are negative amounts, in minor units.

The app wants a badge for the biggest charge that was refunded in full. That means a charge of k and a refund of exactly -k both appear on the statement.

You are asked to find that amount.

Your task

Write largest_matched_amount(amounts).

amounts[i] is one line of the statement. A positive value is a charge. A negative value is a refund. No line is 0.
Return the largest positive k such that both k and -k appear in amounts.
Return -1 if there is no such k.
The statement may repeat an amount. One refund is enough to match a charge of the same size.

Examples

Example 1 (traced)#

text2 lines

Input:  amounts = [900, -1500, 350, -350, -90, 40, 1000, -1200]
Output: 350

Sort the amounts: [-1500, -1200, -350, -90, 40, 350, 900, 1000]. Pointer lo starts at the most negative refund and hi at the largest charge. At each step compare their sizes.

Equal sizes are a match. Otherwise the larger size has no partner and its pointer moves in.

lo	hi	Refund at lo	Charge at hi	Sizes	Move
0	7	-1500	1000	1500 and 1000	the refund is larger: lo becomes 1
1	7	-1200	1000	1200 and 1000	the refund is larger: lo becomes 2
2	7	-350	1000	350 and 1000	the charge is larger: hi becomes 6
2	6	-350	900	350 and 900	the charge is larger: hi becomes 5
2	5	-350	350	350 and 350	equal sizes: return 350

Example 2#

text2 lines

Input:  amounts = [1000, 250, -300]
Output: -1

There is a refund, but no charge of 300. There is no match.

Example 3#

text2 lines

Input:  amounts = [3, -3, 8, -8, 8]
Output: 8

Both 3 and 8 are matched. The largest is 8. The extra charge of 8 changes nothing.

Constraints

1 ≤ amounts.length ≤ 100,000 (lines on one statement)
-1,000,000,000 ≤ amounts[i] ≤ 1,000,000,000, and amounts[i] ≠ 0 (minor units)

What does n ≤ 10^5 tell you?

The answer is at most 1,000,000,000, which fits in a 32-bit integer.