Problem Description

Given an array of positive integers nums and an integer k, find the kth smallest sum of a contiguous subarray of nums. In other words, consider every possible subarray (a subarray is any sequence of consecutive elements from nums), compute their sums, sort these sums in non-decreasing order, and return the sum that is the kth smallest.

• Each subarray must consist of consecutive elements from nums.
• Subarrays can overlap, and elements may be reused in different subarrays, but not within the same subarray.
• There is always at least one valid solution.
• Constraints typically ensure 1 <= nums.length <= 2 * 10^4 and 1 <= nums[i] <= 100, making brute-force enumeration infeasible.

Thought Process

The most direct approach is to generate all possible contiguous subarrays, calculate their sums, collect all these sums, sort them, and pick the kth smallest. However, with up to O(n^2) subarrays and n as large as 20,000, this approach is not practical due to memory and time constraints.

We need to find a way to efficiently determine what the kth smallest subarray sum is, without materializing all subarrays or their sums. This typically suggests a binary search over the range of possible sums, combined with a fast way to count how many subarrays have a sum less than or equal to a given value.

The key insight is to treat the problem as a "kth smallest number in a sorted matrix" problem, where the matrix is implicit and not constructed. By leveraging prefix sums and a two-pointer or sliding window technique, we can efficiently count the number of subarrays whose sum is less than or equal to any target value.

Solution Approach

• Step 1: Binary Search on Answer
  • The minimum possible subarray sum is the smallest element in nums; the maximum is the sum of the whole array.
  • We perform binary search on this range. For each mid-value, we need to determine: "How many subarrays have sum ≤ mid?"
• Step 2: Counting Subarrays with Sum ≤ mid
  • Use a sliding window (two pointers) approach: for each starting index, expand the end pointer until the window sum exceeds mid.
  • For each start, the number of valid subarrays is equal to the number of end pointers for which the sum does not exceed mid.
  • Alternatively, use prefix sums and a moving window to efficiently count valid subarrays in O(n) per check.
• Step 3: Binary Search Logic
  • If the count of subarrays with sum ≤ mid is at least k, we search lower; otherwise, higher.
  • The smallest value for which the count is at least k is our answer.
• Why This Works
  • Binary search reduces the search space logarithmically, and the sliding window counts subarrays efficiently per query.
  • This approach avoids generating all subarray sums, keeping both time and space complexity manageable.

Example Walkthrough

Suppose nums = [2, 1, 3] and k = 4.

1. List all subarrays and their sums:
   [2] = 2
   [2,1] = 3
   [2,1,3] = 6
   [1] = 1
   [1,3] = 4
   [3] = 3
2. All sums: 1, 2, 3, 3, 4, 6 (sorted: 1, 2, 3, 3, 4, 6)
3. The 4th smallest sum is 3.
4. With binary search, we would check mid-values between 1 and 6, and use the sliding window to count how many subarrays have sum ≤ mid, adjusting the search accordingly until we find the answer.

Time and Space Complexity

• Brute-force approach:
  O(n^2) time and space to generate all subarrays and their sums, which is infeasible for large n.
• Optimized approach (binary search + sliding window):
  • Binary search over sum range: O(log(S)), where S is the sum of the array.
  • For each binary search iteration, counting subarrays: O(n).
  • Total: O(n * log(S)) time.
  • Space: O(1) or O(n) if prefix sums are used.

Summary

The Kth Smallest Subarray Sum problem is a classic example where brute-force is infeasible, but a combination of binary search and efficient counting (sliding window) yields an elegant and scalable solution. By leveraging the properties of subarrays and monotonicity, we avoid generating all possible sums and instead home in on the correct answer using efficient algorithms. This approach is both efficient and robust, handling even large input sizes gracefully.

Code Implementation

def kthSmallestSubarraySum(nums, k):
    def countSubarraysWithSumLE(target):
        count = 0
        left = 0
        curr_sum = 0
        for right in range(len(nums)):
            curr_sum += nums[right]
            while curr_sum > target and left <= right:
                curr_sum -= nums[left]
                left += 1
            count += right - left + 1
        return count

    left, right = min(nums), sum(nums)
    answer = -1
    while left <= right:
        mid = (left + right) // 2
        cnt = countSubarraysWithSumLE(mid)
        if cnt >= k:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    return answer
      

int kthSmallestSubarraySum(vector<int>& nums, int k) {
    auto countSubarraysWithSumLE = [&](int target) {
        int count = 0, left = 0, curr_sum = 0;
        for (int right = 0; right < nums.size(); ++right) {
            curr_sum += nums[right];
            while (curr_sum > target && left <= right) {
                curr_sum -= nums[left++];
            }
            count += right - left + 1;
        }
        return count;
    };
    int left = *min_element(nums.begin(), nums.end()), right = accumulate(nums.begin(), nums.end(), 0), answer = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cnt = countSubarraysWithSumLE(mid);
        if (cnt >= k) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return answer;
}
      

public int kthSmallestSubarraySum(int[] nums, int k) {
    int left = nums[0], right = 0;
    for (int num : nums) {
        left = Math.min(left, num);
        right += num;
    }
    int answer = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cnt = countSubarraysWithSumLE(nums, mid);
        if (cnt >= k) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return answer;
}

private int countSubarraysWithSumLE(int[] nums, int target) {
    int count = 0, left = 0, curr_sum = 0;
    for (int right = 0; right < nums.length; ++right) {
        curr_sum += nums[right];
        while (curr_sum > target && left <= right) {
            curr_sum -= nums[left++];
        }
        count += right - left + 1;
    }
    return count;
}
      

function kthSmallestSubarraySum(nums, k) {
    function countSubarraysWithSumLE(target) {
        let count = 0, left = 0, curr_sum = 0;
        for (let right = 0; right < nums.length; ++right) {
            curr_sum += nums[right];
            while (curr_sum > target && left <= right) {
                curr_sum -= nums[left++];
            }
            count += right - left + 1;
        }
        return count;
    }
    let left = Math.min(...nums), right = nums.reduce((a, b) => a + b, 0), answer = -1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let cnt = countSubarraysWithSumLE(mid);
        if (cnt >= k) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return answer;
}