# Kth Smallest Subarray Sum

# Kth Smallest Subarray Sum

Kth Smallest Subarray Sum finds the k-th smallest value among all contiguous subarray sums.

For nonnegative arrays, subarray sums have a monotone structure. This allows binary search on the answer and a sliding window count for how many subarrays have sum at most a candidate value.

## Problem

Given an array $A$ of length $n$ with nonnegative values and a 1-based rank $k$, find the k-th smallest sum among all subarrays:

$$
A[i] + A[i+1] + \dots + A[j]
$$

where:

$$
0 \le i \le j < n
$$

There are:

$$
\frac{n(n+1)}{2}
$$

nonempty subarrays.

## Algorithm

Binary search over possible sum values. For each candidate sum $s$, count how many subarrays have sum at most $s$.

```id="ksss1"
kth_smallest_subarray_sum(A, k):
    low = min(A)
    high = sum(A)

    while low < high:
        mid = floor((low + high) / 2)

        if count_subarrays_at_most(A, mid) < k:
            low = mid + 1
        else:
            high = mid

    return low
```

For nonnegative arrays, the counting step uses a sliding window.

```id="ksss2"
count_subarrays_at_most(A, s):
    count = 0
    left = 0
    current = 0

    for right from 0 to n - 1:
        current = current + A[right]

        while current > s:
            current = current - A[left]
            left = left + 1

        count = count + (right - left + 1)

    return count
```

## Example

Let:

$$
A = [2, 1, 3]
$$

All subarray sums are:

$$
2, 3, 6, 1, 4, 3
$$

Sorted:

$$
[1, 2, 3, 3, 4, 6]
$$

For $k = 4$, the answer is:

$$
3
$$

## Correctness

For a fixed threshold $s$, `count_subarrays_at_most` counts all subarrays whose sum is at most $s$. Because all values are nonnegative, increasing the right endpoint can only increase the current window sum, and moving the left endpoint can only decrease it.

After the while loop, every subarray ending at `right` and starting from any index between `left` and `right` has sum at most $s$. There are exactly `right - left + 1` such subarrays.

The predicate "at least $k$ subarray sums are at most $s$" is monotone. Therefore binary search returns the smallest sum satisfying it, which is the k-th smallest subarray sum.

## Complexity

| step                         |          cost |
| ---------------------------- | ------------: |
| one counting pass            |        $O(n)$ |
| binary search over sum range |   $O(\log S)$ |
| total                        | $O(n \log S)$ |
| space                        |        $O(1)$ |

where:

$$
S = \sum_i A[i]
$$

## When to Use

Use this method when the array contains nonnegative values and generating all subarray sums would be too expensive.

If negative numbers are allowed, the sliding window count no longer works. In that case, use prefix sums with an ordered structure or a divide and conquer counting method.

## Implementation

```id="ksss3"
def count_subarrays_at_most(a, limit):
    count = 0
    left = 0
    current = 0

    for right, x in enumerate(a):
        current += x

        while current > limit:
            current -= a[left]
            left += 1

        count += right - left + 1

    return count

def kth_smallest_subarray_sum(a, k):
    low = min(a)
    high = sum(a)

    while low < high:
        mid = (low + high) // 2

        if count_subarrays_at_most(a, mid) < k:
            low = mid + 1
        else:
            high = mid

    return low
```

```id="ksss4"
func countSubarraysAtMost(a []int, limit int) int {
	count := 0
	left := 0
	current := 0

	for right, x := range a {
		current += x

		for current > limit {
			current -= a[left]
			left++
		}

		count += right - left + 1
	}

	return count
}

func KthSmallestSubarraySum(a []int, k int) int {
	low := a[0]
	high := 0

	for _, x := range a {
		if x < low {
			low = x
		}
		high += x
	}

	for low < high {
		mid := low + (high-low)/2

		if countSubarraysAtMost(a, mid) < k {
			low = mid + 1
		} else {
			high = mid
		}
	}

	return low
}
```