LeetCode · #862
Shortest Subarray with Sum at Least K Solution
Use prefix sums + a monotonic deque to find the shortest valid window in linear time, even when the array contains negative numbers.
01
Section One · Problem
Problem Statement
Return the length of the shortest non-empty subarray whose sum is at least k. If no such subarray exists, return -1.
Example
Input: nums = [2, -1, 2], k = 3 Output: 3 // The whole array sums to 3, and no shorter subarray works.
Why this is tricky
• Negative numbers break a normal sliding window • Expanding right can make the sum go down • We need a smarter way to compare many candidate starts quickly
02
Section Two · Brute Force
Try Every Start — O(n²)
For every starting index, extend the subarray to the right until the sum reaches k. Track the shortest valid length.
Problem: With up to 100,000 elements, O(n²) is far too slow. Also, classic sliding window does not work because negative values can decrease the running sum after expansion.
03
Section Three · Optimal
Prefix Sums + Monotonic Deque — O(n)
Let prefix[i] be the sum of the first i elements. Then the sum of subarray [j, i - 1] is prefix[i] - prefix[j]. We want this to be at least k, and we want i - j as small as possible.
💡 Mental model: Imagine every prefix sum as a checkpoint on a timeline. For the current checkpoint
i, you want the earliest useful checkpoint j such that the height difference prefix[i] - prefix[j] is at least k. The deque stores only the checkpoints that are still worth considering.
Deque invariants
- The deque stores indices of prefix sums.
- Prefix sums in the deque are kept in increasing order.
- If the current prefix sum makes the front valid, pop from the front and update the answer.
- If the current prefix sum is smaller than or equal to the back prefix sum, pop the back because the newer checkpoint is strictly better.
Why increasing prefix sums? If
prefix[a] >= prefix[b] and a < b, then a is worse than b: it has a larger prefix sum and is earlier, so it will never produce a shorter or larger-difference candidate later.
04
Section Four · Walkthrough
Visual Walkthrough
Trace nums = [2, -1, 2], k = 3. Prefix sums are [0, 2, 1, 3].
Monotonic deque over prefix sums
05
Section Five · Code
Code — Java & Python
Java — prefix sum + deque
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int shortestSubarray(int[] nums, int k) {
int n = nums.length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++)
prefix[i + 1] = prefix[i] + nums[i];
Deque<Integer> dq = new ArrayDeque<>();
int ans = n + 1;
for (int i = 0; i <= n; i++) {
while (!dq.isEmpty() && prefix[i] - prefix[dq.peekFirst()] >= k)
ans = Math.min(ans, i - dq.pollFirst());
while (!dq.isEmpty() && prefix[dq.peekLast()] >= prefix[i])
dq.pollLast();
dq.offerLast(i);
}
return ans == n + 1 ? -1 : ans;
}
}
Python — prefix sum + deque
from collections import deque
class Solution:
def shortestSubarray(self, nums: list[int], k: int) -> int:
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)
dq = deque()
ans = len(nums) + 1 for i, cur in enumerate(prefix):
while dq and cur - prefix[dq[0]] >= k:
ans = min(ans, i - dq.popleft())
while dq and prefix[dq[-1]] >= cur:
dq.pop()
dq.append(i)
return -1 if ans == len(nums) + 1 else ans
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Prefix sum + monotonic deque | O(n) | O(n) |
Why O(n)?:
- Each prefix index is appended once, and removed from the front or back at most once.
- That makes the total deque work linear.
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | What happens | Why it matters |
|---|---|---|
| Negative numbers | Still works correctly | This is exactly why we need prefix sums + deque instead of a normal window. |
| No valid subarray | Return -1 | Example: [1, 2], k = 10. |
| Single element already enough | Return 1 | Example: [5], k = 3. |
| Large sums | Use long in Java | Prefix sums can overflow int. |
⚠ Common Mistake: Forgetting the second while-loop that removes larger prefix sums from the back. Without that monotonic cleanup, the deque keeps dominated checkpoints and you lose the O(n) guarantee.