Shortest Subarray with Sum at Least K

Shortest Subarray with Sum at Least K looks like a sliding-window problem, but the array can contain negative numbers — and that one detail breaks the simple window. The fix combines two classic tools: prefix sums and a monotonic deque.

The slow way first

The obvious idea: try every subarray. For each left end, extend right and track the running sum, stopping when it reaches K. That is O(n²) and far too slow for large inputs.

The question to ask: can I express a subarray sum so two endpoints are independent? Yes — with prefix sums. Let prefix[i] be the sum of the first i numbers. Then the sum of nums[l..r-1] is just prefix[r] - prefix[l]. We want the shortest gap r - l where prefix[r] - prefix[l] >= K.

The idea: an increasing deque of prefix indices

Sweep i over the prefix array, keeping a deque of candidate left ends with two rules:

• Pop the front while prefix[i] - prefix[front] >= K. That front gives a valid window, and since we sweep left to right, this is the shortest window ending here for that front — record it and discard the front (a later i would only be longer).
• Pop the back while prefix[back] >= prefix[i]. A later index with a smaller-or-equal prefix is always a better left end, so the old back is useless.

These two rules keep the deque strictly increasing in prefix value, and every index enters and leaves it at most once.

The key insight: a negative number can shrink a prefix, so a later index can be a strictly better left end than an earlier one — which is exactly why we maintain an increasing deque instead of a plain window.

Walk through it

Step through the animation. For nums = [2, -1, 2] the prefix array is [0, 2, 1, 3]. Watch index 1 (prefix 2) get popped from the back when index 2 (prefix 1) arrives, and index 0 get popped from the front when index 3 (prefix 3) reaches a difference of 3 >= K.

Pseudocode

build prefix where prefix[i] = sum of first i numbers
best = infinity
deque dq = empty            # holds indices, increasing prefix values
for i from 0 to len(prefix) - 1:
    while dq and prefix[i] - prefix[dq.front] >= K:
        best = min(best, i - dq.pop_front())
    while dq and prefix[dq.back] >= prefix[i]:
        dq.pop_back()
    dq.push_back(i)
return best if best is finite else -1

The Python solution

def shortest_subarray(nums, K):
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)
    best, dq = len(nums) + 1, deque()
    for i, cur in enumerate(prefix):
        while dq and cur - prefix[dq[0]] >= K:
            best = min(best, i - dq.popleft())
        while dq and prefix[dq[-1]] >= cur:
            dq.pop()
        dq.append(i)
    return best if best <= len(nums) else -1

• prefix is the running-sum array; prefix[i] - prefix[l] is the sum of nums[l..i-1].
• dq holds indices into prefix, kept increasing by prefix value.
• Line 7 is the front drain: every front whose window reaches K yields a candidate length i - front, and we pop it because no later right end gives a shorter window for that front.
• Line 9 is the back drain: an index with prefix >= cur can never be a better left end than i, so we remove it.
• We append i last, so it becomes available as a left end for future right ends.

Complexity

We trade O(n) extra space (the prefix array and deque) for a one-pass solution. The amortized argument is the heart of every monotonic-deque problem: each index is added once and removed once, so the inner while loops are O(n) in total, not O(n²).

When this pattern shows up

Practice