Shortest Subarray with Sum at Least K
Problem
Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum at least k. If no such subarray exists, return -1.
- 1 ≤ nums.length ≤ 10⁵
- −10⁵ ≤ nums[i] ≤ 10⁵
- 1 ≤ k ≤ 10⁹
Example
nums = [2, -1, 2], k = 33We first compute prefix sums so that any subarray sum can be written as a difference of two prefix values. We include prefix[0] = 0 so that subarrays starting at index 0 can be handled naturally. For nums = [2, -1, 2], the prefix sums are: prefix = [0, 2, 1, 3] We iterate through the prefix array while maintaining a deque of indices whose prefix sums are strictly increasing. The deque stores candidate start indices for valid subarrays. - At index 0 (prefix = 0), the deque is empty, so we add index 0. - At index 1 (prefix = 2), the difference 2 - 0 < 3, so no valid subarray exists yet. We append index 1. - At index 2 (prefix = 1), we remove index 1 from the back of the deque because 1 <= 2. A smaller prefix sum at a later index dominates earlier larger ones, since it can form shorter valid subarrays. We then append index 2. - At index 3 (prefix = 3), the difference 3 - 0 >= 3, so we have found a valid subarray of length 3 - 0 = 3. This corresponds to nums[0:3] = [2, -1, 2]. We update the answer to 3. No shorter valid subarray exists, so the final answer is 3.
Approach
Straightforward Solution
A brute-force approach checks all subarrays, summing elements each time, resulting in O(n²) time complexity, which is infeasible for large inputs.
Core Observation
The problem reduces to finding the shortest subarray where the difference between two prefix sums is at least k. This can be reframed as finding indices i < j such that prefix[j] - prefix[i] >= k with minimal j - i.
Path to Optimal
PreviewBy precomputing prefix sums, the problem becomes searching for pairs of indices with a prefix difference at least k…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewCompute prefix sums and iterate through them. Maintain a deque of indices with strictly increasing prefix sums…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each index is pushed and popped from the deque at most once, resulting in linear time traversal of the prefix sums array.
Space
O(n)
The prefix sums array and the deque can each hold up to n+1 elements, leading to O(n) auxiliary space usage.
Pattern Spotlight
Prefix Sums + Monotonic Deque
When searching for the shortest subarray with a sum constraint, transform the problem using prefix sums and maintain a monotonic queue of candidate start indices to efficiently find valid subarrays and discard dominated candidates, ensuring O(n) complexity.
Solution
| 1 | from collections import deque |
| 2 | |
| 3 | class Solution: |
| 4 | def shortestSubarray(self, nums, k: int) -> int: |
| 5 | n = len(nums) |
| 6 | prefix = [0] * (n + 1) |
| 7 | for i in range(n): |
| 8 | prefix[i + 1] = prefix[i] + nums[i] |
| 9 | |
| 10 | q = deque() |
| 11 | ans = n + 1 |
| 12 | |
| 13 | for i in range(n + 1): |
| 14 | while q and prefix[i] - prefix[q[0]] >= k: |
| 15 | ans = min(ans, i - q.popleft()) |
| 16 | |
| 17 | while q and prefix[i] <= prefix[q[-1]]: |
| 18 | q.pop() |
| 19 | |
| 20 | q.append(i) |
| 21 | |
| 22 | return ans if ans <= n else -1 |
Step-by-Step Solution
Compute Prefix Sums to Transform Subarray Sum Queries
| 5 | n = len(nums) |
| 6 | prefix = [0] * (n + 1) |
| 7 | for i in range(n): |
| 8 | prefix[i + 1] = prefix[i] + nums[i] |
Objective
To precompute prefix sums that allow constant-time calculation of any subarray sum.
Key Insight
Prefix sums convert the problem of summing arbitrary subarrays into simple difference queries between two prefix sums. This transformation is essential because it enables the use of a monotonic queue to efficiently find subarrays meeting the sum constraint without recomputing sums repeatedly.
Interview Quick-Check
Core Logic
Prefix sums allow O(1) subarray sum queries by storing cumulative sums up to each index.
Common Pitfalls & Bugs
Off-by-one errors in prefix sum indexing can cause incorrect subarray sums; ensure prefix array length is n+1 with prefix[0] = 0.
Use a Monotonic Queue to Identify Valid Subarrays and Maintain Candidates
To maintain a deque of indices representing prefix sums in increasing order, enabling efficient detection of subarrays with sums at least k and discarding dominated candidates.
Return the Shortest Valid Subarray Length or -1 if None Exists
To finalize the result by returning the minimal subarray length found or -1 if no valid subarray meets the sum requirement.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
while q and prefix[i] - prefix[q[0]] >= k:While the deque is not empty and the current prefix sum minus the prefix sum at the front is at least k, update answer and pop from front.
This loop identifies the shortest subarray ending at i with sum at least k by comparing prefix sums and removes indices that cannot yield shorter subarrays, ensuring minimal length tracking.
while q and prefix[i] <= prefix[q[-1]]:While the deque is not empty and the current prefix sum is less than or equal to the prefix sum at the back, pop from back.
Removing indices with larger or equal prefix sums at the back maintains the deque's increasing order invariant, discarding suboptimal candidates that cannot lead to shorter subarrays.
return ans if ans <= n else -1Return the minimal subarray length if found; otherwise, return -1.
Returning ans if it is within bounds signals a valid subarray was found; returning -1 indicates no such subarray exists, fulfilling the problem requirements.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why does maintaining a deque of indices with increasing prefix sums enable finding the shortest subarray with sum at least k efficiently?
See the answer with Pro.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Shortest Subarray with Sum at Least K from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Shortest Subarray with Sum at Least K drill