Shortest Subarray with Sum at Least K — Monotonic Deque (LeetCode 862)

Shortest Subarray with Sum at Least K (LeetCode 862) is one of the hardest deque problems. It asks for the minimum-length subarray whose sum is at least K. The twist: the array can contain negative numbers, which breaks the standard sliding window approach.

The Problem

Input:  nums = [2, -1, 2], k = 3
Output: 3
Explanation: [2, -1, 2] has sum 3 ≥ k. No shorter subarray works.

Input:  nums = [1], k = 1
Output: 1

Input:  nums = [1, 2], k = 4
Output: -1 (no subarray has sum ≥ 4)

Why Sliding Window Fails

The classic “minimum window with sum >= K” uses a shrinkable sliding window. But that only works when all numbers are non-negative. With negative numbers:

nums = [84, -37, 32, 40, 95], k = 167

A sliding window might shrink past a negative number,
missing a longer subarray that includes it and has a larger sum.

Negative numbers mean adding more elements can decrease the sum, so the monotonicity that sliding window relies on breaks.

Key Insight: Prefix Sums + Monotonic Deque

Define prefix[i] = nums[0] + nums[1] + ... + nums[i-1] (with prefix[0] = 0).

The sum of subarray nums[i..j-1] = prefix[j] - prefix[i].

We want the shortest j - i such that prefix[j] - prefix[i] >= k.

For each j, we want the largest i < j such that prefix[i] <= prefix[j] - k. A monotonic deque helps us find this efficiently.

Two Deque Properties

1. Pop from the front when prefix[j] - prefix[deque[0]] >= k: We found a valid subarray. Record its length and pop the front — any future j' > j would give a longer subarray with the same i, so deque[0] is no longer useful.

2. Pop from the back when prefix[j] <= prefix[deque[-1]]: If a future position needs a small prefix, j is a better candidate than deque[-1] because j is further right (shorter subarray) and has a smaller or equal prefix sum.

Implementation

from collections import deque

def shortestSubarray(nums, k):
    """
    Shortest subarray with sum >= k using monotonic deque.
    Time: O(n), Space: O(n)
    """
    n = len(nums)

    # Build prefix sums
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    result = float('inf')
    dq = deque()  # stores indices into prefix array

    for j in range(n + 1):
        # Pop from front: found valid subarrays
        while dq and prefix[j] - prefix[dq[0]] >= k:
            result = min(result, j - dq[0])
            dq.popleft()

        # Pop from back: maintain increasing prefix sums
        while dq and prefix[j] <= prefix[dq[-1]]:
            dq.pop()

        dq.append(j)

    return result if result != float('inf') else -1

Step-by-Step Trace

nums = [2, -1, 2], k = 3
prefix = [0, 2, 1, 3]

j=0: prefix[0]=0
  deque empty → append 0
  dq = [0]

j=1: prefix[1]=2
  Front check: 2 - 0 = 2 < 3 → no pop
  Back check: 2 > 0 → no pop
  Append 1
  dq = [0, 1]

j=2: prefix[2]=1
  Front check: 1 - 0 = 1 < 3 → no pop
  Back check: 1 < 2 → pop 1  (prefix[2] < prefix[1])
  Back check: 1 > 0 → no pop
  Append 2
  dq = [0, 2]

j=3: prefix[3]=3
  Front check: 3 - 0 = 3 >= 3 → result = min(∞, 3-0) = 3, popleft
  Front check: 3 - 1 = 2 < 3 → stop
  Back check: 3 > 1 → no pop
  Append 3
  dq = [2, 3]

Result = 3

Trace with Negative Numbers

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

j=0: dq=[0]
j=1: prefix=84, 84-0=84<167. dq=[0,1]
j=2: prefix=47, 47<84 → pop 1. dq=[0,2]
j=3: prefix=79, 79>47 → no back pop. dq=[0,2,3]
j=4: prefix=119, 119>79 → no back pop. dq=[0,2,3,4]
j=5: prefix=214
  Front: 214-0=214≥167 → result=5, popleft. dq=[2,3,4]
  Front: 214-47=167≥167 → result=min(5,3)=3, popleft. dq=[3,4]
  Front: 214-79=135<167 → stop
  Back: 214>119 → no pop
  Append 5. dq=[3,4,5]

Result = 3 (subarray nums[2..4] = [32, 40, 95] = 167)

Why the Deque Stays Increasing

If prefix[i] >= prefix[j] where i < j, then for any future index m:

• prefix[m] - prefix[j] >= prefix[m] - prefix[i] (j gives a larger or equal diff)
• m - j < m - i (j gives a shorter subarray)

So j dominates i in both sum and length. We can safely discard i.

Complexity Analysis

Metric	Value
Time	O(n) — each index is added and removed from the deque at most once
Space	O(n) — prefix array and deque

Edge Cases

# Single element >= k
assert shortestSubarray([5], 3) == 1

# No valid subarray
assert shortestSubarray([1, 2], 10) == -1

# All negative
assert shortestSubarray([-1, -2, -3], 1) == -1

# k = 0 with positive elements
assert shortestSubarray([1], 0) == 1

# Large negative followed by large positive
assert shortestSubarray([-100, 200], 100) == 1  # [200] alone

# Negative cancels out
assert shortestSubarray([2, -1, 2], 3) == 3

Comparison with Related Problems

Problem	Negatives?	Approach
Min subarray sum >= k (LC 209)	No	Sliding window O(n)
Shortest subarray sum >= k (LC 862)	Yes	Monotonic deque O(n)
Max subarray sum (LC 53)	Yes	Kadane’s O(n)
Subarray sum equals k (LC 560)	Yes	Prefix sum + hash map O(n)

When to Use This Pattern

Use monotonic deque + prefix sums when:

• You need the shortest subarray with a sum constraint
• The array contains negative numbers (ruling out sliding window)
• You need prefix[j] - prefix[i] >= k for the closest j - i
• The problem involves optimizing over all subarrays with a sum threshold

Common Mistakes

1. Using sliding window — fails with negatives, gives wrong answers
2. Forgetting prefix[0] = 0 — the prefix array has n+1 elements
3. Wrong deque ordering — must maintain increasing prefix sums
4. Not checking both front and back — both conditions are essential for O(n)

Related Problems

Problem	Key Difference
Minimum Size Subarray Sum (LC 209)	Non-negative only, sliding window
Maximum Subarray (LC 53)	Max sum, not shortest length
Subarray Sum Equals K (LC 560)	Exact sum, not “at least”
Sliding Window Maximum (LC 239)	Monotonic deque for max values

Key Takeaways

• Negative numbers break the sliding window approach for sum constraints
• Prefix sums transform subarray sums into differences: sum(i..j) = prefix[j+1] - prefix[i]
• A monotonic increasing deque of prefix-sum indices lets us find optimal pairs in O(n)
• Front pops find valid subarrays; back pops maintain the increasing invariant
• This is one of the most elegant applications of the monotonic deque pattern