Shortest Subarray with Sum at Least K
Shortest Subarray with Sum at Least K is a hard monotonic stack problem solved with the monotonic stack pattern.
The best approach, optimal (prefix sums + monotonic deque), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (every start, extend to the right) up.
Problem
Given an integer array nums and an integer k, return the length of the shortest non-empty contiguous subarray whose elements add up to at least k. If no such subarray exists, return -1.
The array may contain negative numbers, so making a window longer does not always make its sum larger.
Examples
Example 1
- Input
nums = [3, -1, 4, -2, 6], k = 8- Output
3- Why
- [4, -2, 6] sums to 8 with length 3. No window of length 1 or 2 reaches 8 (the best pair is 4 + -2 = 2 or -2 + 6 = 4).
Example 2
- Input
nums = [5, -10, 2, 9], k = 11- Output
2- Why
- [2, 9] sums to exactly 11. Starting earlier only adds the -10, which makes things worse.
Example 3
- Input
nums = [1, -1, 1], k = 3- Output
-1- Why
- The largest sum of any contiguous piece is 1, so no subarray reaches 3.
Constraints
1 <= nums.length <= 10^5-10^5 <= nums[i] <= 10^51 <= k <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (every start, extend to the right) | O(n²) | O(1) |
| Optimal (prefix sums + monotonic deque) | O(n) | O(n) |
1Brute force (every start, extend to the right)
O(n²)In the worst case every (start, end) pair is visited.O(1)A running sum and the best length.For each start index, add elements one by one and stop at the first end where the running sum reaches k. That is the shortest window for that start; keep the best over all starts.
- best = infinity.
- For each i: sum = 0; for j from i: sum += nums[j]; if sum >= k, best = min(best, j - i + 1) and break.
- Return best, or -1 if it was never updated.
class Solution {
public int shortestSubarray(int[] nums, int k) {
int n = nums.length;
int best = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
long sum = 0;
for (int j = i; j < n && j - i + 1 < best; j++) {
sum += nums[j];
if (sum >= k) {
best = j - i + 1;
break;
}
}
}
return best == Integer.MAX_VALUE ? -1 : best;
}
}class Solution:
def shortestSubarray(self, nums: List[int], k: int) -> int:
n = len(nums)
best = float("inf")
for i in range(n):
total = 0
j = i
while j < n and j - i + 1 < best:
total += nums[j]
if total >= k:
best = j - i + 1
break
j += 1
return -1 if best == float("inf") else bestclass Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
int n = nums.size();
int best = INT_MAX;
for (int i = 0; i < n; i++) {
long long sum = 0;
for (int j = i; j < n && j - i + 1 < best; j++) {
sum += nums[j];
if (sum >= k) {
best = j - i + 1;
break;
}
}
}
return best == INT_MAX ? -1 : best;
}
};function shortestSubarray(nums, k) {
const n = nums.length;
let best = Infinity;
for (let i = 0; i < n; i++) {
let sum = 0;
for (let j = i; j < n && j - i + 1 < best; j++) {
sum += nums[j];
if (sum >= k) {
best = j - i + 1;
break;
}
}
}
return best === Infinity ? -1 : best;
}2Optimal (prefix sums + monotonic deque)
O(n)Each index is pushed once and popped at most once.O(n)The prefix-sum array and the deque hold up to n + 1 entries.Build prefix sums P[0..n]. Scan j from 0 to n, keeping a deque of indices whose prefix sums strictly increase from front to back. While P[j] - P[front] >= k, the front is a valid start for j and no later j could give it a shorter window, so record j - front and pop it. Then, while P[back] >= P[j], pop the back: j is a later, no-larger start, so it dominates. Push j.
- P[0] = 0, P[i + 1] = P[i] + nums[i], using long.
- For j from 0 to n: while deque not empty and P[j] - P[front] >= k: best = min(best, j - front), pop front.
- While deque not empty and P[back] >= P[j]: pop back.
- Push j at the back. At the end return best, or -1.
class Solution {
public 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;
int best = Integer.MAX_VALUE;
for (int j = 0; j <= n; j++) {
while (head < tail && pre[j] - pre[dq[head]] >= k) {
best = Math.min(best, j - dq[head]);
head++;
}
while (head < tail && pre[dq[tail - 1]] >= pre[j]) tail--;
dq[tail++] = j;
}
return best == Integer.MAX_VALUE ? -1 : best;
}
}class Solution:
def shortestSubarray(self, 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 j in range(n + 1):
while dq and pre[j] - pre[dq[0]] >= k:
best = min(best, j - dq.popleft())
while dq and pre[dq[-1]] >= pre[j]:
dq.pop()
dq.append(j)
return -1 if best == n + 1 else bestclass Solution {
public:
int shortestSubarray(vector<int>& nums, int k) {
int n = nums.size();
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
vector<int> dq(n + 1);
int head = 0, tail = 0;
int best = INT_MAX;
for (int j = 0; j <= n; j++) {
while (head < tail && pre[j] - pre[dq[head]] >= k) {
best = min(best, j - dq[head]);
head++;
}
while (head < tail && pre[dq[tail - 1]] >= pre[j]) tail--;
dq[tail++] = j;
}
return best == INT_MAX ? -1 : best;
}
};function shortestSubarray(nums, k) {
const n = nums.length;
const pre = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
const dq = new Int32Array(n + 1);
let head = 0, tail = 0;
let best = Infinity;
for (let j = 0; j <= n; j++) {
while (head < tail && pre[j] - pre[dq[head]] >= k) {
best = Math.min(best, j - dq[head]);
head++;
}
while (head < tail && pre[dq[tail - 1]] >= pre[j]) tail--;
dq[tail++] = j;
}
return best === Infinity ? -1 : best;
}Edge cases to test
- A single element already >= k (answer 1)
- No valid subarray at all (answer -1)
- Negative numbers in the middle, which break the usual shrinking sliding window
- Prefix sums that exceed the int range when added up, so use long
Hints
Hint 1
With prefix sums P, the subarray (i, j] has sum P[j] - P[i]. You want the closest i before j with P[i] <= P[j] - k.
Hint 2
If i1 < i2 and P[i1] >= P[i2], then i1 is never a better start than i2 for any later j: i2 is closer and gives a larger sum. Drop i1.
Hint 3
Keep candidate start indices in a deque with increasing prefix sums. Pop from the front while it forms a valid subarray with j (it can never do better later), and pop from the back while its prefix is >= P[j].
FAQ
What is the best time complexity for Shortest Subarray with Sum at Least K?
Optimal (prefix sums + monotonic deque) runs in O(n) time and O(n) extra space. Each index is pushed once and popped at most once.
Which pattern does Shortest Subarray with Sum at Least K use?
It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.
Is there a brute force solution for Shortest Subarray with Sum at Least K?
Yes. Brute force (every start, extend to the right) takes O(n²) time and O(1) space. For each start index, add elements one by one and stop at the first end where the running sum reaches k.
Which edge cases should I test for Shortest Subarray with Sum at Least K?
A single element already = k (answer 1); No valid subarray at all (answer -1); Negative numbers in the middle, which break the usual shrinking sliding window; Prefix sums that exceed the int range when added up, so use long.