Shortest Subarray with Sum at Least K — Problem & Solution
Shortest Subarray with Sum at Least K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Shortest Subarray with Sum at Least K is a hard coding problem on arrays, binary search and prefix sum, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Binary Search, Prefix Sum, Sliding Window, Monotonic Queue
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return the length of the shortest non-empty subarray of nums whose sum is at least k, or 0 if there is none.
(Negative values are allowed, which is what makes this harder than the all-positive version.)
Example 1
Input: nums = [1], k = 1
Output: 1
Example 2
Input: nums = [1,2], k = 4
Output: 0
Explanation: The whole array only sums to 3.
Example 3
Input: nums = [2,-1,2], k = 3
Output: 3
Explanation: The -1 forces the window to span everything.
Constraints
1 <= nums.length <= 100000-100000 <= nums[i] <= 1000001 <= k <= 1000000000
Hints for Shortest Subarray with Sum at Least K
Hint 1
With negative values a plain two-pointer window fails — extending a window can lower its sum.
Hint 2
Work with prefix sums: you need indices
i < jwithpre[j] - pre[i] >= kandj - iminimal.Hint 3
Keep the candidate
ivalues in a deque that stays strictly increasing in prefix sum.
How to solve Shortest Subarray with Sum at Least K
Reduce to prefix sums and keep a monotonic deque of candidate left endpoints. Two rules prune it: a candidate already satisfied can be retired (nothing later will beat it), and a candidate with a prefix sum at least as large as a newer one is useless.
Approach
- Build
pre[0…n]withpre[i+1] = pre[i] + nums[i]. - For each
i, whilepre[i] - pre[dq.front()] >= k, recordi - dq.front()and pop the front. - While
pre[dq.back()] >= pre[i], pop the back — a later index with a smaller prefix sum dominates. - Push
i. Return the best length, or0if none was found.
Why it works
Popping the front is safe because any later right end paired with that index gives a longer subarray, and it is already satisfied. Popping the back is safe because a smaller prefix sum at a larger index is better on both counts: it yields a bigger difference and a shorter span. The deque therefore stays increasing in prefix sum, and each index is pushed and popped once.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- A sliding window without the deque is wrong here — negative numbers break the monotonicity.
- Prefix sums reach
10^5 · 10^5 = 10^10, so they need 64-bit. - The answer for 'no such subarray' is
0, not-1.
Reference solution
Python
from collections import deque
from typing import List
def shortestSubarray(nums: List[int], k: int) -> int:
n = len(nums)
pre = [0] * (n + 1)
for i in range(n):
pre[i + 1] = pre[i] + nums[i]
dq = deque()
best = n + 1
for i in range(n + 1):
while dq and pre[i] - pre[dq[0]] >= k:
best = min(best, i - dq.popleft())
while dq and pre[dq[-1]] >= pre[i]:
dq.pop()
dq.append(i)
return best if best <= n else 0Java
public static int shortestSubarray(int[] nums, int k) {
int n = nums.length;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
int[] dq = new int[n + 1];
int head = 0, tail = 0, best = n + 1;
for (int i = 0; i <= n; i++) {
while (tail > head && pre[i] - pre[dq[head]] >= k) {
best = Math.min(best, i - dq[head]);
head++;
}
while (tail > head && pre[dq[tail - 1]] >= pre[i]) tail--;
dq[tail++] = i;
}
return best <= n ? best : 0;
}C++
int shortestSubarray(vector<int>& nums, int k) {
int n = (int) nums.size();
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
deque<int> dq;
int best = n + 1;
for (int i = 0; i <= n; i++) {
while (!dq.empty() && pre[i] - pre[dq.front()] >= k) {
best = min(best, i - dq.front());
dq.pop_front();
}
while (!dq.empty() && pre[dq.back()] >= pre[i]) dq.pop_back();
dq.push_back(i);
}
return best <= n ? best : 0;
}JavaScript
var shortestSubarray = function(nums, k) {
var n = nums.length;
var pre = [0];
for (var i = 0; i < n; i++) pre.push(pre[i] + nums[i]);
var dq = [];
var head = 0;
var best = n + 1;
for (var j = 0; j <= n; j++) {
while (dq.length > head && pre[j] - pre[dq[head]] >= k) {
var len = j - dq[head];
head++;
if (len < best) best = len;
}
while (dq.length > head && pre[dq[dq.length - 1]] >= pre[j]) dq.pop();
dq.push(j);
}
return best <= n ? best : 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search