Shortest Subarray with Sum at Least K
Understanding the Problem
We need to find the shortest contiguous subarray whose sum is at least k. If this problem only had positive numbers, a standard sliding window would do the job because expanding the window always increases the sum and shrinking always decreases it. But the presence of negative numbers breaks that monotonic property. Shrinking the window can increase the sum (by dropping a negative element), and expanding it can decrease the sum.
This rules out a plain two-pointer approach. We need a way to track which starting points are still worth considering as we move through the array.
Prefix sums combined with a monotone deque solve this in linear time. For any subarray nums[i..j], its sum equals prefix[j+1] - prefix[i]. So finding a subarray with sum at least k is equivalent to finding indices i < j where prefix[j] - prefix[i] >= k and j - i is minimized.
Key Constraints:
1 <= nums.length <= 10^5-- With up to 100,000 elements, we need O(n) or O(n log n). Anything quadratic will time out.-10^5 <= nums[i] <= 10^5-- Negative numbers are present. This rules out the standard sliding window approach since the window sum isn't monotonically related to window size.1 <= k <= 10^9-- k can be large, so it's possible no valid subarray exists.- A prefix sum can reach
10^5 * 10^5 = 10^10, which overflows a 32-bit integer. The accumulator and prefix array must use a 64-bit type (long/long long/int64).
Approach 1: Brute Force
Intuition
Check every possible subarray. For each starting index i, extend the subarray to the right, accumulating the sum. The first ending index j where the running sum reaches at least k gives the shortest valid subarray that starts at i, because j only grows as we extend, so the first crossing has the smallest length. Once that happens, we can stop extending from this start and move on to the next one.
Negative numbers do not break this inner-loop logic. They only mean we cannot stop scanning starting indices early: a later start can still produce a shorter valid subarray, so we must try all of them.
Algorithm
- Initialize
minLength = infinity. - For each starting index
ifrom 0 to n-1: - Initialize
currentSum = 0. - For each ending index
jfromito n-1: - Add
nums[j]tocurrentSum. - If
currentSum >= k, updateminLength = min(minLength, j - i + 1)and break. - If
minLengthis still infinity, return -1. Otherwise, returnminLength.
Example Walkthrough
Input:
With k = 3, we scan every starting index and extend until the running sum reaches 3.
- Start
i = 0: sum atj=0is 2 (below 3), atj=1is 1 (below 3), atj=2is 3 (reaches 3). Length2 - 0 + 1 = 3. RecordminLength = 3, break. - Start
i = 1: sum atj=1is -1, atj=2is 1. Never reaches 3. No update. - Start
i = 2: sum atj=2is 2. Never reaches 3. No update.
Only the subarray from index 0 to 2 qualifies, so the answer is 3.
Code
- Time Complexity: O(n^2). For each of the n starting positions, we potentially scan up to n elements. In the worst case, we scan the entire array from every starting point.
- Space Complexity: O(1). We only use a few variables regardless of input size.
The brute force recomputes overlapping sums and discards what it learns between starting indices. The next approach precomputes prefix sums once and uses a deque to find the best starting point for each ending position in amortized constant time.
Approach 2: Prefix Sum + Monotone Deque
Intuition
Reformulate the problem in terms of prefix sums. Define prefix[0] = 0 and prefix[j] = nums[0] + nums[1] + ... + nums[j-1]. The sum of subarray nums[i..j-1] is prefix[j] - prefix[i], so we need the smallest j - i such that prefix[j] - prefix[i] >= k with i < j.
For a fixed j, the best starting point is the largest i (closest to j) such that prefix[i] <= prefix[j] - k. Not all indices are worth keeping as candidates.
Consider two indices i1 < i2 where prefix[i1] >= prefix[i2]. Index i1 is dominated by i2 for every future j: i2 gives a subarray sum that is at least as large (its prefix is smaller or equal) and a shorter subarray (it sits closer to any endpoint). So i1 can be discarded. The surviving candidates form a strictly increasing sequence of prefix sums, which we maintain in a deque ordered by index.
Once prefix[j] - prefix[i] >= k for the index i at the front of the deque, we record the length and remove i permanently. Any later j' > j paired with the same i would only produce a longer subarray, so i has already given its shortest answer.
The two while loops are nested inside the for loop, but the total work is still linear. Each index j is pushed onto the deque exactly once, and it can be removed at most once, either from the front (when it produces a valid subarray) or from the back (when a smaller prefix sum dominates it). Across all n+1 iterations, the number of pop operations is bounded by the number of pushes, so the while loops do O(n) work in total.
Algorithm
- Build the prefix sum array where
prefix[j] = nums[0] + nums[1] + ... + nums[j-1]. - Initialize an empty deque and
minLength = infinity. - For each index
jfrom 0 to n: - While the deque is not empty and
prefix[j] - prefix[deque.front()] >= k: - Update
minLength = min(minLength, j - deque.front()). - Pop from the front (this index has given its best answer).
- While the deque is not empty and
prefix[j] <= prefix[deque.back()]: - Pop from the back (maintaining the increasing prefix sum property).
- Push
jonto the back of the deque. - Return
minLengthif it was updated, otherwise -1.
Example Walkthrough
Code
- Time Complexity: O(n). Building the prefix sum array takes O(n). Each index is pushed onto and popped from the deque at most once, so the deque operations across all iterations total O(n).
- Space Complexity: O(n). The prefix sum array uses O(n) space. The deque can hold at most n+1 indices, so it also uses O(n) space.