Shortest Subarray with Sum at Least K — Hard Problem & Solution

Return the length of the shortest non-empty subarray of nums whose sum is at least k, or 0 if there is none.

Difficulty: Hard
Topics: Arrays, Binary Search, Sliding Window, Prefix Sum, 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] <= 100000
1 <= k <= 1000000000

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] with pre[i+1] = pre[i] + nums[i].
For each i, while pre[i] - pre[dq.front()] >= k, record i - 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, or 0 if 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue