Shortest Subarray with Sum ≥ K

Interview Prep

HardSliding Window Variation of Sliding Window Maximumarraysmonotonic-dequeprefix-sum

The problem

Given an integer array (possibly containing negative values) and an integer k, return the length of the shortest contiguous non-empty subarray whose sum is at least k. Return −1 if no such subarray exists.

Why sliding window doesn't work here

The textbook sliding-window approach for non-negative arrays advances the right pointer to grow the sum, then advances the left pointer to shrink. That depends on monotonicity: adding an element can only increase the sum, removing one can only decrease. Negative elements break both invariants — advancing the right pointer can decrease the sum, and we can't safely shrink from the left. 

def shortest_sum_at_least_k_wrong(nums, k):
    """Sliding window — works when nums are non-negative, FAILS with negatives."""
    n = len(nums)
    lo, total, best = 0, 0, n + 1
    for hi in range(n):
        total += nums[hi]
        while total >= k:
            best = min(best, hi - lo + 1)
            total -= nums[lo]; lo += 1
    return -1 if best == n + 1 else best

# nums = [2, -1, 2], k = 3:
# Expected: 3 (sum 2-1+2 = 3).
# Sliding window thinks: at hi=0, total=2 < 3.
#   hi=1, total=1.  hi=2, total=3 -> shrink: lo=0, total=1.  Done.  best=3 ✓
# Lucky.  But:
# nums = [84, -37, 32, 40, 95], k = 167:
# True answer = 3 (indices 2,3,4: 32+40+95 = 167).
# Sliding window's "shrink while >=k" can advance lo past a NEGATIVE element,
# missing the optimum window that started earlier.

Pattern: monotonic deque over prefix sums

Reframe the question in terms of prefix sums. A subarray nums[i..j] has sum prefix[j+1] − prefix[i]. We want the shortest pair of indices i < j with prefix[j] − prefix[i] ≥ k.

Two moves at each step:

Each index is pushed and popped at most once. Total work O(n).

Solution

from collections import deque

def shortest_subarray(nums: list[int], k: int) -> int:
    """O(n).  Monotonic deque on PREFIX SUMS.
    The deque holds indices i such that prefix[i] is strictly increasing.
    """
    n = len(nums)
    prefix = [0] * (n + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x

    dq: deque[int] = deque()       # indices into prefix, values strictly increasing
    best = n + 1

    for i in range(n + 1):
        # 1) Try to shrink from the FRONT: while prefix[i] - prefix[dq[0]] >= k, we have a window
        while dq and prefix[i] - prefix[dq[0]] >= k:
            best = min(best, i - dq.popleft())
        # 2) Maintain increasing: pop from BACK anything >= prefix[i]
        while dq and prefix[dq[-1]] >= prefix[i]:
            dq.pop()
        dq.append(i)

    return -1 if best == n + 1 else best

Trace

nums = [84, -37, 32, 40, 95], k = 167
prefix = [0, 84, 47, 79, 119, 214]
                                ^^^   prefix[5] = 214

i=0, prefix[0]=0:    dq is empty. push 0.  dq=[0].
i=1, prefix[1]=84:   prefix[1]-prefix[0]=84 < 167.
                     back-maintain: 0 < 84 ok. push 1.  dq=[0, 1].
i=2, prefix[2]=47:   prefix[2]-prefix[0]=47 < 167.
                     back-maintain: prefix[1]=84 >= 47, pop 1.
                                    prefix[0]=0  >= 47? no.   push 2.  dq=[0, 2].
i=3, prefix[3]=79:   prefix[3]-prefix[0]=79 < 167.
                     back: prefix[2]=47 < 79 ok.  push 3.  dq=[0, 2, 3].
i=4, prefix[4]=119:  prefix[4]-prefix[0]=119 < 167.
                     back: prefix[3]=79 < 119 ok. push 4.  dq=[0, 2, 3, 4].
i=5, prefix[5]=214:  prefix[5]-prefix[0]=214 >= 167 -> window len 5-0=5. best=5. pop 0.
                     prefix[5]-prefix[2]=167 >= 167 -> window len 5-2=3. best=3. pop 2.
                     prefix[5]-prefix[3]=135 < 167.
                     back: prefix[4]=119 < 214 ok. push 5.

return best = 3   (indices 3..5 in nums = [32, 40, 95])

Complexity

Why "pop from the back when prefix[tail] ≥ prefix[i]"

Consider two candidate "start" indices j < i with prefix[j] ≥ prefix[i]. For any future r, prefix[r] − prefix[i] ≥ prefix[r] − prefix[j], so i dominates j for the "≥ k" test; and the window starting at i is also shorter (since i > j). So j is useless and can be dropped. This is the load-bearing invariant of the deque.

Why "pop from the front when window-sum ≥ k"

Symmetric reasoning. If dq[0] achieves the threshold against the current i, recording its length is enough — any later i' would yield a strictly longer window, so dq[0] is never useful again. Pop it.

Same trick in the wild