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:

where:

There are:

nonempty subarrays.

Algorithm

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

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.

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:

All subarray sums are:

Sorted:

For $k = 4$, the answer is:

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

where:

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

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

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
}