Shortest Subarray with Sum At Least K — Monotonic Deque on Prefix Sums

Problem Statement#

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of the array.

Constraints:

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5
• 1 <= k <= 10^9

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

Input:  nums = [1,2], k = 4
Output: -1

Input:  nums = [2,-1,2], k = 3
Output: 3

Why This Problem Matters#

LeetCode 862 Shortest Subarray with Sum At Least K is widely considered one of the cleanest hard-tier monotonic deque problems and shows up at Amazon, Google, Meta, and Two Sigma. It is the natural generalization of Minimum Size Subarray Sum (LeetCode 209) when the array can contain negative numbers — the standard sliding window pattern breaks because expanding the window can decrease the sum.

This problem teaches the most important advanced sliding window technique: a monotonic deque maintained over prefix sums. Recruiters specifically use this problem to test whether the candidate has internalized the connection between prefix sums and subarray queries, and whether they can adapt the deque pattern when the input has both positive and negative values.

The Core Insight#

Compute prefix sums P where P[0] equals 0 and P[i] equals nums[0] plus ... plus nums[i minus 1]. The sum of a subarray nums[i..j minus 1] equals P[j] minus P[i]. We want the smallest j minus i such that P[j] minus P[i] is greater than or equal to k.

For each right endpoint j, we want the largest i less than j with P[i] less than or equal to P[j] minus k. This is a classic deque problem:

1. Maintain a deque of indices with strictly increasing prefix sums from front to back.
2. For each j, while the front satisfies P[j] minus P[front] greater than or equal to k, record the candidate answer j minus front and pop the front (we will never get a shorter subarray ending later by using this front again).
3. While the back has prefix sum greater than or equal to P[j], pop the back. Reason: any future right endpoint j' with P[j'] minus P[back] greater than or equal to k will also satisfy P[j'] minus P[j] greater than or equal to k (since P[j] is less than or equal to P[back]) and use a shorter subarray — so back is dominated.
4. Push j onto the back.

Each index is pushed and popped at most once, giving O(n).

Visual Dry Run#

nums equals [2, -1, 2], k equals 3. Prefix sums P equal [0, 2, 1, 3].

Final answer 3.

Solution (Optimal)#

We use deque from collections in Python, and an array with head and tail pointers in JavaScript for O(1) deque operations.

from collections import deque
from typing import List
 
def shortestSubarray(nums: List[int], k: int) -> int:
    n = len(nums)
    P = [0] * (n + 1)
    for i in range(n):
        P[i + 1] = P[i] + nums[i]
 
    dq = deque()  # indices into P, monotonic increasing P values
    best = n + 1
 
    for j in range(n + 1):
        # Pull answers from the front while feasible
        while dq and P[j] - P[dq[0]] >= k:
            best = min(best, j - dq.popleft())
        # Maintain monotonic increasing P values from front to back
        while dq and P[dq[-1]] >= P[j]:
            dq.pop()
        dq.append(j)
 
    return best if best <= n else -1

function shortestSubarray(nums, k) {
  const n = nums.length;
  const P = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) P[i + 1] = P[i] + nums[i];
 
  const dq = new Array(n + 1);
  let head = 0, tail = 0;
  let best = n + 1;
 
  for (let j = 0; j <= n; j++) {
    while (head < tail && P[j] - P[dq[head]] >= k) {
      best = Math.min(best, j - dq[head++]);
    }
    while (head < tail && P[dq[tail - 1]] >= P[j]) tail--;
    dq[tail++] = j;
  }
 
  return best <= n ? best : -1;
}

Complexity. Time O(n) because every index is pushed and popped at most once. Space O(n) for the prefix sum array and deque.

Common Mistakes#

• Trying to use a standard two-pointer sliding window. It fails because negative numbers can shrink the running sum, breaking the monotonicity that two pointers rely on.
• Forgetting to pop the front aggressively — once a front yields an answer, any later j will give a longer subarray with that front, so popping is correct.
• Using greater-than-only when cleaning the back. Equality must also pop because two equal prefix sums are dominated by the rightmost (shorter subarray).
• Using a Python list with pop(0) — that is O(n) per operation and times out.
• Off-by-one errors in the prefix sum array. Always allocate length n plus 1 with P[0] equal to 0.

Interview Tips#

• Begin by explicitly contrasting with LeetCode 209 (all positives, two-pointer works) and explain why negatives break the sliding window.
• Walk through the deque invariants on the whiteboard: front gives smallest P, back is the most recent index, all P values increase from front to back.
• Mention that the deque stores indices into P, not into nums, which trips up many candidates.
• Be prepared to derive the time bound: each index pushed once, popped at most once from front or back, totaling O(n) operations.
• Discuss the alternative segment tree approach (O(n log n)) and why the deque is preferred.

Follow-up Questions#

1. What if all numbers are non-negative? The two-pointer sliding window solves it in O(n) with O(1) extra space.
2. What if k can be negative? Empty subarrays are not allowed; check for any single element greater than or equal to k early.
3. What if you want all subarrays summing to at least k? Output the count instead — modify the front popping to count rather than track minimum.
4. What if you must support online updates (insert and append)? Use a balanced BST or segment tree on prefix sums.
5. What about the longest subarray with sum less than or equal to k? Symmetric problem; reverse comparison and run a max-monotonic deque.

Key Takeaways#

• Negative numbers break the standard sliding window — a monotonic deque on prefix sums is the go-to.
• The deque holds indices into the prefix sum array, maintaining increasing prefix sums from front to back.
• Pop the front whenever it yields a feasible answer; you will never need that front again.
• Pop the back whenever the new prefix sum is less than or equal — older, larger sums are dominated.
• Time O(n), space O(n) — strictly better than O(n log n) segment tree solutions.
• This pattern is the FAANG signature for "shortest subarray with sum constraint" problems.