Kth smallest subarray sum

Array Binary Search Sliding Window

53.4% acceptance

Mar 31, 2026

225

Given an integer array nums of length n and an integer k, return the kth smallest subarray sum. A subarray is defined as a non-empty contiguous sequence of elements in an array. A subarray sum is the sum of all elements in the subarray.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn kth_smallest_subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let mut lo = *nums.iter().min().unwrap();
    let mut hi: i32 = nums.iter().sum();
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      let mut count = 0i64;
      let mut sum = 0i32;
      let mut left = 0;
      for right in 0..n {
        sum += nums[right];
        while sum > mid {
          sum -= nums[left];
          left += 1;
        }
        count += (right + 1 - left) as i64;
      }
      if count >= k as i64 {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
}