Shortest Subarray with Sum at Least K (LC 862) — Prefix Sum + Monotonic Deque

Problem Statement#

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

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.

The array may contain negative numbers, which is what makes this problem hard.

Constraints:

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

Example 1:

Input:  nums = [1], k = 1
Output: 1
Explanation: The subarray [1] has sum = 1 >= 1.

Example 2:

Input:  nums = [1, 2], k = 4
Output: -1
Explanation: Maximum subarray sum is 3 < 4.

Example 3:

Input:  nums = [2, -1, 2], k = 3
Output: 3
Explanation: Only [2, -1, 2] (the whole array) has sum 3 >= 3.
             The shorter subarrays [2], [-1], [2], [2,-1], [-1,2] all sum below 3.

Why This Problem Matters#

This is a canonical hard problem that reveals a deep gap in understanding. Most candidates correctly reach for a sliding window after converting to prefix sums — but then realize that negative numbers break the two-pointer approach. In a purely positive array, a growing prefix sum means we can always shrink from the left. With negatives, a prefix can decrease, creating windows that are non-monotone in sum. A plain sliding window cannot handle this.

The solution — a monotone increasing deque on prefix sums — is a beautiful fusion of two concepts. It appears in system design contexts like shortest time-to-metric-threshold in telemetry streams, minimum-cost subarrays in financial analytics, and range queries on signed data. Google and Amazon regularly use variants of this problem to test candidates' ability to extend familiar patterns to non-standard settings.

The Core Insight#

Define prefix sums: P[0] = 0, P[i] = nums[0] + ... + nums[i-1]. The sum of subarray nums[l..r-1] is P[r] - P[l]. We want the smallest r - l such that P[r] - P[l] >= k.

Key observation: if P[j] >= P[i] and j > i, then index i can never be a better left boundary than j for any future right boundary. Because P[j] >= P[i] means removing the prefix up to j subtracts at least as much as removing the prefix up to i, so the resulting subarray sum is smaller — and the subarray is also longer. We can safely discard i.

This observation gives us a monotone increasing deque of prefix sum indices. For each new right boundary r:

1. Collect answers: While the front index l satisfies P[r] - P[l] >= k, record length r - l, and pop l from the front. We pop because a later right boundary can only produce a longer answer for the same left boundary.
2. Maintain monotone property: Pop back indices j while P[j] >= P[r]. These are dominated (as explained above).
3. Push r onto the back.

Each index is pushed and popped at most once → O(n) total.

Visual Dry Run#

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

Prefix sums: P = [0, 2, 1, 3]

Minimum length = 3. Answer = 3.

Trace for r=2 in detail: deque is [0,1], P[2]=1. Pop back: P[1]=2 >= P[2]=1, so pop 1. Push 2 → deque is [0,2]. No answer collected because P[2]-P[0]=1 < 3.

Common Mistakes#

1. Using a plain sliding window. With negative numbers, a prefix sum does not grow monotonically. Shrinking the left when the sum is too small can accidentally skip valid windows. The deque is required.

2. Using prefix sums of length n instead of n+1. Define P with n+1 elements where P[0] = 0. This makes P[r] - P[l] represent the sum of nums[l..r-1] cleanly. Using n elements forces awkward index arithmetic.

3. Popping the front for monotone maintenance (wrong side). The front is popped when a valid answer is found. The back is popped for monotone maintenance. Mixing up the sides produces wrong results.

4. Not popping the front eagerly. Once P[r] - P[dq.front()] >= k, you should keep popping the front as long as the condition holds — each additional pop might yield a shorter valid subarray (smaller l, same r, larger length is worse, so we want to push l as far right as possible). Wait — actually we want the shortest subarray, so popping the front eagerly is correct: after we pop left boundary l and record length r-l, is there a shorter answer using the same r but a later l? Yes — so keep popping.

5. Forgetting to initialize ans = n + 1 (or infinity) and then checking whether it was updated before returning. If no valid subarray exists, return -1, not n+1.

6. Integer overflow. nums[i] can reach 10^5 in magnitude and the array can have 10^5 elements, so prefix sums can reach 10^10. Use long in Java/C++ or Python (which handles big ints natively).

7. Confusing this problem with LC 209 (positive-only). LC 209 can be solved with a simple two-pointer window. LC 862 requires the deque because of negative numbers. Citing the wrong algorithm in an interview signals insufficient depth.

Solutions#

Python#

from collections import deque
 
def shortestSubarray(nums: list[int], k: int) -> int:
    n = len(nums)
 
    # Build prefix sum array of length n+1
    # P[i] = nums[0] + nums[1] + ... + nums[i-1]
    # Sum of nums[l..r-1] = P[r] - P[l]
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
 
    dq = deque()   # monotone increasing deque of prefix-sum indices
    ans = n + 1    # sentinel value larger than any valid answer
 
    for r in range(n + 1):
        # Step 1: collect answers
        # while the subarray from dq.front() to r has sum >= k,
        # record its length and pop the front (it cannot give a shorter
        # answer for any later right boundary)
        while dq and prefix[r] - prefix[dq[0]] >= k:
            ans = min(ans, r - dq.popleft())
 
        # Step 2: maintain monotone increasing deque
        # if the back index has a prefix sum >= prefix[r],
        # it is dominated and can be discarded
        while dq and prefix[dq[-1]] >= prefix[r]:
            dq.pop()
 
        # Step 3: push current index onto the back
        dq.append(r)
 
    # If ans was never updated, no valid subarray exists
    return ans if ans <= n else -1

JavaScript#

var shortestSubarray = function(nums, k) {
    const n = nums.length;
 
    // Build prefix sum array P of length n+1
    // P[0] = 0, P[i] = P[i-1] + nums[i-1]
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
 
    const dq = [];      // monotone increasing deque of indices into prefix[]
    let ans = n + 1;    // sentinel; any valid answer is <= n
 
    for (let r = 0; r <= n; r++) {
        // Step 1: pop front while subarray sum from front to r meets the target
        // each pop gives a candidate answer; we want the minimum length
        while (dq.length > 0 && prefix[r] - prefix[dq[0]] >= k) {
            ans = Math.min(ans, r - dq.shift());  // dq.shift() removes from front
        }
 
        // Step 2: pop back while prefix[back] >= prefix[r]
        // those back indices are dominated: same or worse sum, farther left
        while (dq.length > 0 && prefix[dq[dq.length - 1]] >= prefix[r]) {
            dq.pop();   // remove dominated index from back
        }
 
        // Step 3: push current index; maintain the monotone property
        dq.push(r);
    }
 
    // Return -1 if no valid subarray was found
    return ans <= n ? ans : -1;
};

Complexity Analysis#

Each of the n+1 prefix indices is pushed onto the deque exactly once and popped at most once, so the total work across all deque operations is O(n). Building the prefix sum array is also O(n).

Follow-up Questions#

1. What if all numbers are positive? Use the classic two-pointer sliding window (LC 209). No deque needed. The key difference is that positive arrays have monotone-growing prefix sums, allowing a safe left-shrink whenever the sum is too large.

2. What if you need the maximum sum subarray instead of minimum length? That is Kadane's algorithm — O(n) with no prefix sum structure needed. It does not generalize to a fixed-sum threshold query.

3. What if you need the shortest subarray with sum exactly k? This is harder. For positive numbers, a two-pointer works. For general integers, use a hash map on prefix sums to find P[r] - P[l] == k — but finding the shortest such subarray requires storing the first occurrence of each prefix value.

4. Can you solve this with a heap? A min-heap on (prefix[l], l) works: for each r, pop entries where prefix[r] - prefix[l] >= k and record r - l. But heap operations are O(log n), giving O(n log n) total — worse than the O(n) deque approach.

5. How would you handle a stream (online setting)? The deque naturally processes elements left to right with O(1) amortized per element, making it suitable for streaming. You only need the prefix sum up to the current position.

This Pattern Solves#

• LC 862 — Shortest Subarray with Sum at Least K (this problem)
• LC 239 — Sliding Window Maximum (deque for running maximum)
• LC 1499 — Max Value of Equation (deque with linear objective)
• LC 1438 — Longest Continuous Subarray With Absolute Diff <= Limit (two deques)
• LC 209 — Minimum Size Subarray Sum (positive-only, simpler two-pointer version)

Key Takeaway#

When negative numbers break the two-pointer invariant, convert to prefix sums and apply a monotone increasing deque. Pop the front to collect valid answers (shortest subarray found so far); pop the back to maintain the monotone property (discard dominated left boundaries). The result is an O(n) algorithm that handles arbitrary integers elegantly. Recognizing when a plain sliding window fails — and knowing that a deque on prefix sums is the fix — is the hallmark of a senior-level problem solver.

Key Takeaways#

• LC 862 is a hard problem that extends LC 209 (positive numbers only) to arbitrary integers — negative values break the standard shrinkable window, requiring a deque on prefix sums.
• Convert to prefix sums: prefix[j] - prefix[i] >= k with i < j means the subarray [i, j-1] has sum at least k; we want to minimize j - i.
• Maintain a monotone increasing deque of prefix-sum indices: pop from the back any index i where prefix[i] >= prefix[j] before pushing j — i is dominated (larger prefix, later index).
• Pop from the front when prefix[j] - prefix[deque[front]] >= k: this is a valid answer; record j - deque.popleft() and keep popping because more pops can only give shorter subarrays.
• Time O(n), space O(n) — each index is pushed and popped from the deque at most once.
• The front-pop is for collecting answers; the back-pop is for maintaining the monotone invariant — never confuse the two.
• This deque-on-prefix-sums pattern also solves LC 239 (sliding window maximum), LC 1499 (max value of equation), and LC 1438 (absolute diff limit) — the same deque structure with different monotone directions.