788. The kth Smallest Sum of a Contiguous Run

Given n POSITIVE integers, consider every contiguous run a[i..j] with i <= j. There are n (n + 1) / 2 of them. Print the kth smallest run total, counting from 1.

list 1 2 3 4, k = 5 -> 4 totals 1 2 3 3 4 5 6 7 9 10 list 1 2 3 4, k = 1 -> 1 list 2 2 2 2 2, k = 8 -> 4 five 2s, four 4s, three 6s, two 8s, one 10 list 3 1 4 1 5 9 2, k = 12 -> 8

## Listing the totals is quadratic

At n = 10^5 there are about 5 * 10^9 runs. Even producing them with a prefix-sum array is hopeless; only the ranked total is wanted.

## Counting runs whose total is at most x

Because every value is POSITIVE, extending a run strictly increases its total, and that is what lets a single window do the counting:

left = 0, sum = 0, count = 0 for right in 0 .. n-1: sum += a[right] while sum > x: sum -= a[left]; left += 1 count += right - left + 1

For each right end, left is the earliest start whose run still fits, so every start from left to right gives a run within the budget, which is right - left + 1 of them. left never retreats, so the pass is O(n).

## Why positivity is not a decoration

With a zero or a negative value in the list, extending a run can LOWER its total, the window's left edge would have to move backwards, and the count above is simply wrong. The constraint that every value is at least 1 is what the whole counter rests on, and noticing which constraint a technique depends on is the point of this problem.

## Why the count is monotone

Raising x cannot disqualify a run that already fitted, so the count is non-decreasing in x.

## Why the answer is a run total that really occurs

Search for the smallest x with count(x) >= k. Then count(x - 1) < k, so some run totals something in (x - 1, x], and sums of integers are integers, so a run totals exactly x. The list 2 2 2 2 2 is the one to trace: its totals are 2, 4, 6, 8, 10 with multiplicities 5, 4, 3, 2, 1, so count never equals many values of k and only the lower-bound form works.

## The bounds

lo is the smallest single value, which is the smallest possible run total. hi is the total of everything, which is the largest. Both are exact and both are reachable, since k may be 1 or n (n + 1) / 2.

## The boundary that breaks a careless implementation

count += right - left + 1, with the + 1, because the single-element run a[right..right] counts too. Dropping it undercounts by exactly n on every guess, which shifts the answer upwards on most inputs and looks like an off-by-one in the search rather than in the counter.

The inner while can empty the window entirely when a single value exceeds x; then left becomes right + 1, sum is 0, and right - left + 1 is 0. That is correct and needs no special case, but it does need the loop written so that left may pass right.

## Relationship with problem 787

787 counts with the same window walked the same way: a right end advances, a left end chases it and never retreats, and the qualifying starts for a given right end are the contiguous block between the two. What keeps the left end from retreating is different in each. 787 SORTS first, so widening the right end can only push the left edge rightwards; here the order is fixed, because runs have to be contiguous, and POSITIVITY does the same job by making every extension raise the total.

The other difference is the + 1. 787 adds hi - lo, because a pair needs two distinct positions and hi cannot pair with itself; this adds right - left + 1, because the one-element run a[right..right] is a run like any other.

## Overflow

Values reach 10^5 and n reaches 10^5, so the total of everything reaches 10000000000 and the number of runs reaches n (n + 1) / 2 = 5000050000. Both are past 2^31 - 1, so hi, the window sum, k and the running count are all 64-bit.

The last test in the list forces both at once, which is the only way to know the claim is worth anything: a hundred thousand copies of 100000 with k at its maximum. The answer is 10000000000, and a build with every long long replaced by int prints 0.

## Cost

Time O(n log(total)). Space O(n).

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