Kth Smallest Subarray Sum - Video Solutions

Problem Overview: Given an array of positive integers, return the kth smallest sum among all possible contiguous subarrays. Instead of listing every subarray explicitly, the goal is to determine the rank of subarray sums efficiently.

Approach 1: Brute Force Enumeration (O(n² log n) time, O(n²) space)

Generate every possible subarray and compute its sum. You iterate over all start indices and extend the subarray to the right while maintaining a running sum. Store each sum in a list, then sort the list and return the element at index k-1. This approach is easy to implement and demonstrates the full search space of arrays, but it becomes impractical for large n because the number of subarrays grows to n(n+1)/2.

Approach 2: Prefix Sum + Min Heap (O(n log n + k log n) time, O(n) space)

Precompute prefix sums so any subarray sum can be calculated quickly. Treat each starting index as a sorted list of possible subarray sums and push the smallest candidate for each start into a min heap. Repeatedly pop the smallest sum and push the next subarray extension for that start index. This technique is similar to merging sorted lists and allows you to extract the kth smallest sum without generating all possibilities. The heap keeps the smallest candidates available at each step.

Approach 3: Binary Search + Sliding Window (O(n log S) time, O(1) space)

The optimal approach avoids generating subarrays entirely. Instead, binary search the answer over the possible sum range [min(nums), sum(nums)]. For a candidate sum mid, count how many subarrays have sum ≤ mid. Because all numbers are positive, a sliding window works: expand the right pointer while maintaining a running sum, and shrink the left pointer when the sum exceeds mid. Every valid window contributes right - left + 1 subarrays ending at right. This counting step runs in O(n). Combine it with binary search over the sum space to locate the smallest value whose count is at least k.

Recommended for interviews: Binary Search + Sliding Window. Interviewers expect you to recognize that the answer space can be searched instead of enumerating subarrays. The sliding window counting trick converts a potentially quadratic enumeration into a linear check, producing an overall O(n log S) solution. Mentioning the brute force first shows understanding of the problem space, but implementing the binary search approach demonstrates stronger algorithmic intuition.