627. The Largest Pair That Stays Under the Limit
Given n integers and a limit, choose two of them by position whose sum is AT MOST the limit,
and make that sum as large as possible.
Print the largest such sum, or -1 when no pair fits.
1 2 3 4, limit 5 -> 5 from 1 + 4 or 2 + 3
1 2, limit 2 -> -1 the only pair sums to 3
2 4 6 8, limit 11 -> 10 from 2 + 8 or 4 + 6
## The sweep
Sort, converge, and keep the best sum that fits:
i = 0, j = n-1, best = -1
while i < j:
s = a[i] + a[j]
if s <= limit:
best = max(best, s)
i += 1
else:
j -= 1
## Why each move is safe
If s > limit, then a[j] is too large for every partner that remains, because a[i] is the
smallest one left. a[j] is in no valid pair at all, so retiring it loses nothing. That is the
605 argument unchanged.
If s <= limit, the pair is valid and has been recorded. Now a[i] cannot do better: a[j]
is the largest partner it has left, so every other pairing of a[i] gives a SMALLER sum, which
is valid but worse. So a[i] is finished and i advances.
That second half is the part people skip. It is not enough that the pair fits; you also have to
argue that nothing better involves a[i], and the argument is that a[j] was already its best
partner.
## Why -1 is a safe sentinel
Values may be negative, so a genuine answer can be negative too: -5 1 3 with limit 0 answers
-2. So -1 cannot simply mean "nothing found" by being small.
It works here because the statement RESERVES it: -1 is printed only when no pair fits, and a
real answer of -1 is indistinguishable but harmless, since both are printed the same way.
When that is not acceptable, the usual fix is a separate boolean, which the reference solutions
use internally.
## Boundaries
Two values are the smallest input, and the answer is their sum or -1.
A limit below every possible sum answers -1.
## Overflow
Sums reach 2 * 10^9 in magnitude. Check that against the limit rather than assuming: a
signed 32 bit integer runs from -2147483648 to 2147483647, so both 2000000000 and
-2000000000 FIT, with about seven percent to spare. This problem has no overflow.
There is a smaller trap next door that is real. Ranking candidates by magnitude means taking
an absolute value, and abs of -2147483648 does not fit in a signed 32 bit integer, so
that is the one input which breaks the call. It cannot arise here, because no sum reaches
past -2 * 10^9, but being able to say WHY it cannot is the part worth having.
## Cost
Time O(n log n) for the sort. Space O(1) beyond the input.
Constraints - `2 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - `-10^9 ≤ limit ≤ 10^9`
Input
The first line contains two integers n and limit.
The second line contains n integers.
Output
Print one integer, the largest pair sum that is at most the limit, or -1 if no pair fits.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.