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.
Example 1:
Input: nums = [2,1,3], k = 4 Output: 3 Explanation: The subarrays of [2,1,3] are: - [2] with sum 2 - [1] with sum 1 - [3] with sum 3 - [2,1] with sum 3 - [1,3] with sum 4 - [2,1,3] with sum 6 Ordering the sums from smallest to largest gives 1, 2, 3, 3, 4, 6. The 4th smallest is 3.
Example 2:
Input: nums = [3,3,5,5], k = 7 Output: 10 Explanation: The subarrays of [3,3,5,5] are: - [3] with sum 3 - [3] with sum 3 - [5] with sum 5 - [5] with sum 5 - [3,3] with sum 6 - [3,5] with sum 8 - [5,5] with sum 10 - [3,3,5], with sum 11 - [3,5,5] with sum 13 - [3,3,5,5] with sum 16 Ordering the sums from smallest to largest gives 3, 3, 5, 5, 6, 8, 10, 11, 13, 16. The 7th smallest is 10.
Constraints:
n == nums.length1 <= n <= 2 * 1041 <= nums[i] <= 5 * 1041 <= k <= n * (n + 1) / 2Problem 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.
We observe that all elements in the array are positive integers. The larger the subarray sum s, the more subarrays there are with sums less than or equal to s. This monotonicity allows us to use binary search to solve the problem.
We perform binary search on the subarray sum, initializing the left and right boundaries as the minimum value in the array nums and the sum of all elements in the array, respectively. Each time, we calculate the number of subarrays with sums less than or equal to the current middle value. If the count is greater than or equal to k, it means the current middle value s might be the k-th smallest subarray sum, so we shrink the right boundary. Otherwise, we increase the left boundary. After the binary search ends, the left boundary will be the k-th smallest subarray sum.
The problem reduces to calculating the number of subarrays in an array with sums less than or equal to s, which we can compute using a function f(s).
The function f(s) is calculated as follows:
j and i, representing the left and right boundaries of the current window, with j = i = 0. Also, initialize the sum of elements in the window t = 0.cnt to record the number of subarrays with sums less than or equal to s, initially cnt = 0.nums. For each element nums[i], add it to the window, i.e., t = t + nums[i]. If t > s, move the left boundary of the window to the right until t leq s, i.e., repeatedly execute t -= nums[j] and j = j + 1. Then update cnt as cnt = cnt + i - j + 1. Continue to the next element until the entire array is traversed.Finally, return cnt as the result of the function f(s).
Time complexity is O(n times log S), where n is the length of the array nums, and S is the sum of all elements in the array nums. Space complexity is O(1).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n² log n) | O(n²) | Small arrays or when demonstrating the baseline approach |
| Prefix Sum + Min Heap | O(n log n + k log n) | O(n) | Useful when extracting the first k smallest sums without scanning all subarrays |
| Binary Search + Sliding Window | O(n log S) | O(1) | Best general solution when the array contains positive integers |
1918 Kth Smallest Subarray Sum (binary search + sliding window) • LetsCode • 781 views views
Watch 2 more video solutions →Practice Kth Smallest Subarray Sum with our built-in code editor and test cases.
Practice on FleetCode