Shortest Subarray with Sum at Least K

Hard Monotonic Stack Monotonic Stack Original on LeetCode

Reported atGoldman Sachs

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^5
  • 1 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(n²)In the worst case every (start, end) pair is visited.
SpaceO(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.

  1. best = infinity.
  2. For each i: sum = 0; for j from i: sum += nums[j]; if sum >= k, best = min(best, j - i + 1) and break.
  3. 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;
    }
}

2Optimal (prefix sums + monotonic deque)

TimeO(n)Each index is pushed once and popped at most once.
SpaceO(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.

  1. P[0] = 0, P[i + 1] = P[i] + nums[i], using long.
  2. For j from 0 to n: while deque not empty and P[j] - P[front] >= k: best = min(best, j - front), pop front.
  3. While deque not empty and P[back] >= P[j]: pop back.
  4. 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;
    }
}

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.