783. The kth Smallest Pair Total

Given n integers, form the total a[i] + a[j] for every pair of POSITIONS with i < j. There are n (n - 1) / 2 such totals, duplicates and all. Print the kth smallest of them, counting from 1.

list 1 2 3 4, k = 3 -> 5 totals 3 4 5 5 6 7 list 1 2 3 4, k = 6 -> 7 list 4 4 4 4 4, k = 1 -> 8 every pair totals 8 list -3 -1 0 2 9, k = 4 -> -1 totals -4 -3 -1 -1 1 2 6 8 9 11

Pairs are positions, not values. Two equal values at different positions form a real pair, and 4 4 4 4 4 has ten of them.

## Listing the totals is quadratic

n reaches 10^5, so there are about 5 * 10^9 totals. Neither the time nor the memory to hold them exists. Only the ranked one is wanted, so only counting is needed.

## Counting totals at most x in one pass

Sort the values first. Then for a threshold x:

lo = 0, hi = n - 1, count = 0 while lo < hi: if a[lo] + a[hi] <= x: count += hi - lo lo += 1 else: hi -= 1

When a[lo] + a[hi] <= x, every partner between lo + 1 and hi is at most a[hi], so every one of those hi - lo pairs also totals at most x, and position lo is finished. When the sum is too big, a[hi] is too big for every remaining partner, so hi can be dropped. Each step retires one index, so the pass is O(n).

## Why the count is monotone

Raising x never disqualifies a pair that already qualified, so count is non-decreasing in x. Nothing about the data is needed beyond that.

## Why the answer is a total that really occurs

Search for the smallest x with count(x) >= k. Then count(x - 1) < k, so at least one pair totals something in (x - 1, x]; totals of integers are integers, so a pair totals exactly x. The list 4 4 4 4 4 is the case to check by hand: count is 0 below 8 and 10 from 8 onwards, so no k in 1..10 ever produces a count equal to k, and only the lower-bound form lands on 8.

## The bounds

After sorting, the smallest total is a[0] + a[1] and the largest is a[n-2] + a[n-1]. Any wider pair of bounds also works and costs a couple of extra iterations.

## The boundary that breaks a careless implementation

The step adds hi - lo, not hi - lo + 1. When a[lo] + a[hi] fits, position lo pairs with positions lo + 1 through hi, which is hi - lo partners; lo paired with itself is not a pair and must not be counted. The extra + 1 inflates every count by the number of left positions still alive, the search converges early, and the answer comes back too small. On 1 2 3 4 with k = 3 it returns 4, and the third smallest total is 5.

The loop condition while lo < hi reads like the same mistake and is not. At lo == hi the increment hi - lo is 0, so while lo <= hi adds nothing to any count and still terminates; it is the + 1 that does the damage, not the comparison. Worth knowing which of the two you are actually protecting against.

## Overflow

Two values of 10^9 total 2000000000, inside the 2147483647 a signed integer held in 32 bits reaches. The two quantities that are not inside it:

count up to n (n - 1) / 2 = 4999950000 at n = 100000 hi - lo up to 4000000000 on a list of -10^9 and 10^9

k is allowed to reach that count, so k, the running count and the bounds are all 64-bit, and the count is the one most often left as an int. The last test in the list forces both at once: fifty thousand copies of -10^9 followed by fifty thousand copies of 10^9, with k at its maximum. The answer is 2000000000, and a build with every long long replaced by int prints 0.

## Where else this lives in the bank

Problem 787 runs the same search over |a[i] - a[j]| instead of a[i] + a[j], and the counter becomes a sliding window rather than two pointers closing in. Reading them side by side is the fastest way to see which part of the technique is fixed and which part is the problem.

## Cost

Time O(n log n + n log(range)). Space O(n).

Constraints - `2 ≤ n ≤ 100000` - `1 ≤ k ≤ n * (n - 1) / 2` - `-10^9 ≤ a[i] ≤ 10^9`