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
By precomputing prefix sums, the problem becomes searching for pairs of indices with a prefix difference at least k. Using a monotonic queue (deque) to store indices of prefix sums in increasing order allows efficient identification of valid subarrays and discarding of suboptimal candidates. This approach reduces the time complexity to O(n) by ensuring each index is pushed and popped at most once.
Optimal Approach
Compute prefix sums and iterate through them. Maintain a deque of indices with strictly increasing prefix sums. For each prefix sum at index i, pop from the front of the deque while the difference with prefix[i] is at least k, updating the answer with the minimal subarray length. Also, pop from the back while the current prefix sum is less than or equal to the prefix sum at the deque's end to maintain monotonicity. Append the current index to the deque. Return the minimal length found or -1 if none exists.
Time
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
| 10 | q = deque() |
| 11 | ans = n + 1 |
| 13 | for i in range(n + 1): |
| 14 | while q and prefix[i] - prefix[q[0]] >= k: |
| 15 | ans = min(ans, i - q.popleft()) |
| 17 | while q and prefix[i] <= prefix[q[-1]]: |
| 18 | q.pop() |
| 20 | q.append(i) |
Objective
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.
Key Insight
The monotonic queue ensures that prefix sums are strictly increasing, which allows the algorithm to quickly find the smallest subarray length satisfying the sum constraint by comparing the current prefix sum with the smallest prefix sums in the queue. Removing indices with larger prefix sums that are no longer useful prevents redundant checks and guarantees linear time complexity.
Interview Quick-Check
Core Logic
The deque stores indices of prefix sums in increasing order, enabling O(1) access to the smallest prefix sums to check sum constraints.
State & Boundaries
Pop from the front while the current prefix sum minus the prefix sum at the front is at least k, updating the answer with the minimal subarray length.
Common Pitfalls & Bugs
Failing to pop from the back when the current prefix sum is less than or equal to the prefix sum at the back leads to incorrect candidates and potential inefficiency.
Complexity
Each index is pushed and popped at most once, ensuring O(n) time complexity.
Return the Shortest Valid Subarray Length or -1 if None Exists
| 22 | return ans if ans <= n else -1 |
Objective
To finalize the result by returning the minimal subarray length found or -1 if no valid subarray meets the sum requirement.
Key Insight
If the answer remains larger than the array length, it indicates no subarray satisfies the sum constraint. Returning -1 signals this to the caller. Otherwise, the minimal length found during iteration is returned, representing the shortest subarray with sum at least k.
Interview Quick-Check
Core Logic
Return the minimal subarray length if found; otherwise, return -1 to indicate no valid subarray.
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.
q = deque()Initialize an empty deque to store indices of prefix sums.
The deque will maintain indices of prefix sums in increasing order, enabling efficient subarray sum checks and candidate management.
ans = min(ans, i - q.popleft())Update the answer with the minimal length between current answer and the subarray length found.
Taking the minimum ensures the algorithm tracks the shortest valid subarray length encountered so far.
q.pop()Pop the last index from the deque to maintain monotonicity.
This operation enforces the strict increasing order of prefix sums in the deque, which is critical for correctness and efficiency.
prefix = [0] * (n + 1)Initialize the prefix sums array with zeros, length n+1.
Prefix sums array length n+1 with prefix[0] = 0 allows for clean calculation of subarray sums as differences between prefix sums.
prefix[i + 1] = prefix[i] + nums[i]Update prefix sum at position i+1 with cumulative sum.
Assigning prefix[i+1] = prefix[i] + nums[i] ensures prefix sums correctly represent cumulative sums up to index i.
ans = n + 1Initialize answer variable with a value larger than any possible subarray length.
Setting ans to n+1 acts as a sentinel to track the minimal subarray length found; if it remains unchanged, no valid subarray exists.
q.append(i)Append the current index i to the deque.
Adding the current index as a candidate start for future subarrays preserves the monotonic queue structure and enables future sum checks.
for i in range(n + 1):Iterate through all prefix sum indices from 0 to n inclusive.
This loop examines each prefix sum to find valid subarrays ending at index i and to maintain the monotonic queue invariant.
for i in range(n):Iterate through nums to build prefix sums.
This loop accumulates the sum of elements up to each index, enabling O(1) subarray sum queries later.
n = len(nums)Calculate the length of the input array nums.
Caching the length avoids repeated calls to len(nums) and clarifies the size of the problem for subsequent operations.
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?
Because the deque stores candidate start indices with increasing prefix sums, it allows quick identification of the earliest prefix sum that satisfies the sum constraint with the current prefix sum, ensuring minimal subarray length and enabling discarding of suboptimal candidates that cannot lead to shorter valid subarrays.
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