Shortest Subarray with Sum at Least K [Hard] — Prefix Sums + Monotonic Deque Explained

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. Return -1 if no such subarray exists. The array may contain negative numbers.

Examples:

Input:  nums = [2, -1, 2], k = 3
Output: 3
Reason: The only subarray with sum >= 3 is [2, -1, 2] (sum = 3), length 3
 
Input:  nums = [1], k = 1
Output: 1
Reason: [1] has sum 1 >= 1, length 1
 
Input:  nums = [1], k = 2
Output: -1
Reason: No subarray can reach sum 2 from [1]
 
Input:  nums = [2, -1, 2, 3], k = 3
Output: 1
Reason: [3] alone has sum 3 >= 3, length 1 — shortest possible

Constraints:

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

Why This Problem Matters#

LeetCode 862 is a Hard problem that appears frequently at Amazon, Google, and Meta because it is a clever trap problem. It looks — at first glance — like a classic two-pointer sliding window problem (similar to LeetCode 209: Minimum Size Subarray Sum). Most candidates dive straight into a sliding window and fail. Only candidates who understand why sliding window breaks on negative numbers, and how prefix sums plus a deque fix it, pass the interview.

Here is the core tension: the classic "shrink from left when sum is too large" shrinking logic of a sliding window depends entirely on one assumption — adding more elements can only increase the sum. The moment you allow negative numbers, that assumption collapses. A longer subarray can have a smaller sum than a shorter one. The window cannot be shrunk greedily.

This problem is also important because it introduces the monotonic deque on prefix sums pattern — a technique that also solves sliding window maximum, largest rectangle problems, and several hard DP optimizations. Understanding this problem unlocks an entire family of techniques.

Interview frequency: This exact problem appears in Amazon OA packages and is a documented Google phone screen question. The pattern (monotonic deque + prefix sums) is asked in various disguises at FAANG companies multiple times per year.

Why This Problem Matters (Negative Numbers Break Normal Sliding Window)#

Let us make this concrete. Take nums = [84, -37, 32, 40, 95], k = 167.

The correct answer is 3: the subarray [32, 40, 95] has sum 167.

Now watch what happens if you try a standard two-pointer sliding window:

left=0, right=0: window=[84],            sum=84  (< 167, expand right)
left=0, right=1: window=[84,-37],        sum=47  (< 167, expand right)
left=0, right=2: window=[84,-37,32],     sum=79  (< 167, expand right)
left=0, right=3: window=[84,-37,32,40],  sum=119 (< 167, expand right)
left=0, right=4: window=[84,-37,32,40,95], sum=214 (>= 167! record len=5, shrink left)
left=1, right=4: window=[-37,32,40,95], sum=130 (< 167, stuck — cannot expand further)

Result: 5. Wrong. The correct answer is 3.

The problem is that shrinking from the left removed the 84 (helpful) but left the -37 (harmful). The -37 is dragging the window sum down, but the sliding window has no way to skip over it and "start fresh" from index 2. The window must always be a contiguous block with contiguous endpoints.

This is the fundamental reason why you need a completely different approach.

The Prefix Sum + Monotonic Deque Insight#

The key insight is a reformulation. Instead of thinking about subarrays directly, convert to prefix sums.

Define P[i] as the sum of the first i elements:

P[0] = 0
P[1] = nums[0]
P[2] = nums[0] + nums[1]
...
P[i] = nums[0] + nums[1] + ... + nums[i-1]

Then the sum of the subarray from index l to r-1 (inclusive) is exactly P[r] - P[l].

So we want: find the minimum r - l such that P[r] - P[l] >= k.

This transforms the problem into a question about pairs of indices in the prefix sum array.

Now, how do we find this efficiently? A naive double loop over all pairs (l, r) is O(n^2) — too slow for n = 10^5.

The monotonic deque optimization:

Process prefix sums left to right. Maintain a deque of indices into the prefix array, where the deque is kept in strictly increasing order of prefix sum values (monotonically increasing). This is the core invariant.

At each new index i:

1. Pop from the front (finding valid subarrays): While the front of the deque j satisfies P[i] - P[j] >= k, we have found a valid subarray of length i - j. Record this length and pop j from the front. We pop because any future index i' > i that also satisfies the condition would give a longer subarray — so j is no longer useful once it has been matched.

2. Pop from the back (maintaining the monotone invariant): While the back of the deque j satisfies P[j] >= P[i], pop it. Why? Because j < i (it came earlier), and P[j] >= P[i] means that i is a strictly better left endpoint for any future right endpoint: it gives a larger difference (more likely to reach k) AND a shorter subarray length. j is dominated and can be discarded forever.

3. Push i to the back of the deque.

The key insight for step 2 is: if we have two left-endpoint candidates j1 < j2 where P[j1] >= P[j2], then for any future right endpoint r, the pair (j2, r) is strictly better than (j1, r):

• P[r] - P[j2] >= P[r] - P[j1] — at least as much sum (actually more, since P[j2] is smaller)
• r - j2 < r - j1 — strictly shorter subarray

So j1 can never contribute to the optimal answer once j2 exists. Discard it.

This gives O(n) overall — each index is pushed and popped at most once.

Visual Dry Run#

Let us trace through nums = [2, -1, 2], k = 3 step by step.

Build prefix sums:

Index:   0   1   2   3
nums:        2  -1   2
P:       0   2   1   3

Process each index i from 0 to 3:

i = 0, P[0] = 0:

• Deque is empty — no front-pop checks.
• Back-pop: deque is empty — nothing to pop.
• Push 0 to back.
• Deque: [0] (stores indices; P values: [0])

i = 1, P[1] = 2:

• Front-pop: P[1] - P[deque[0]] = 2 - 0 = 2. Is 2 >= 3? No. Stop.
• Back-pop: P[deque[-1]] = P[0] = 0. Is 0 >= P[1] = 2? No. Stop.
• Push 1 to back.
• Deque: [0, 1] (P values: [0, 2])

i = 2, P[2] = 1:

• Front-pop: P[2] - P[deque[0]] = 1 - 0 = 1. Is 1 >= 3? No. Stop.
• Back-pop: P[deque[-1]] = P[1] = 2. Is 2 >= P[2] = 1? Yes! Pop index 1.
  • (Index 1 is dominated: any future r that can use index 1 as left can use index 2 instead — shorter length, same or better sum.)
• Back-pop again: P[deque[-1]] = P[0] = 0. Is 0 >= 1? No. Stop.
• Push 2 to back.
• Deque: [0, 2] (P values: [0, 1])

i = 3, P[3] = 3:

• Front-pop: P[3] - P[deque[0]] = 3 - 0 = 3. Is 3 >= 3? Yes! Length = 3 - 0 = 3. Record ans = 3. Pop index 0.
• Front-pop again: P[3] - P[deque[0]] = 3 - P[2] = 3 - 1 = 2. Is 2 >= 3? No. Stop.
• Back-pop: P[deque[-1]] = P[2] = 1. Is 1 >= P[3] = 3? No. Stop.
• Push 3 to back.
• Deque: [2, 3] (P values: [1, 3])

Final answer: 3. Correct — the subarray nums[0..2] = [2, -1, 2] has sum 3.

Notice that at step i=2, we discarded index 1 (P=2) in favor of index 2 (P=1). Even though index 2 is later in the array (so it produces shorter subarrays when used as left endpoint), it has a smaller prefix sum — meaning any future right endpoint will have a higher difference. Index 1 was completely dominated.

Common Mistakes#

Mistake 1: Trying a Standard Sliding Window#

This is the most common interview error. Candidates who have solved LeetCode 209 (Minimum Size Subarray Sum) try to apply the same two-pointer approach. It will silently produce wrong answers on arrays with negative numbers, and the bug is hard to catch unless you specifically test for negatives. Always recognize: negative numbers = no shrinking shortcut = need a different approach.

Mistake 2: Using deque.pop() from the Wrong End#

The two deque operations (front-pop for valid subarrays, back-pop for maintaining monotonicity) are distinct and must target the correct ends. Swapping them — popping from the back to find valid subarrays, or from the front to maintain monotonicity — produces completely incorrect results. A useful mnemonic: "front for answers, back for cleanup."

Mistake 3: Forgetting to Still Push After Front-Pops#

After popping indices from the front because P[i] - P[j] >= k, you still need to go through the back-pop phase and then push i. A common bug is breaking out of the loop early, thinking that once you've found a match, you're done with index i. You are not — i is still a valid future left-endpoint candidate and must be added to the deque.

Mistake 4: Off-by-One in Prefix Sum Array Size#

The prefix sum array has n + 1 elements (indices 0 through n), not n. The loop must run from i = 0 to i = n inclusive. Using range(n) instead of range(n + 1) misses the last element of the array and can produce a wrong or -1 answer even when a valid subarray exists.

Mistake 5: Using int Instead of long (in Typed Languages)#

In Python this is not an issue since integers are arbitrary precision. But in JavaScript and typed languages, the prefix sum can reach 10^5 * 10^5 = 10^10, which overflows a 32-bit integer. Always use BigInt in JavaScript or long long in C++. In the JavaScript solution below, the values are within JavaScript's safe integer range (2^53 - 1), so standard number is fine here — but be aware of this in interviews.

Solutions#

Brute Force — O(n^2) Time, O(n) Space#

Try every possible subarray by iterating over all (l, r) pairs. This establishes the baseline and is worth mentioning in an interview before jumping to the optimal solution.

Python:

from typing import List
 
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
 
        # Build prefix sums: P[i] = sum of nums[0..i-1]
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
 
        ans = float('inf')  # track the minimum subarray length found
 
        # Try every pair of left endpoint l and right endpoint r
        for l in range(n + 1):
            for r in range(l + 1, n + 1):
                # Sum of subarray nums[l..r-1] is P[r] - P[l]
                if prefix[r] - prefix[l] >= k:
                    ans = min(ans, r - l)  # r - l is the subarray length
 
        # If no valid subarray was found, return -1
        return ans if ans != float('inf') else -1

JavaScript:

function shortestSubarray(nums, k) {
    const n = nums.length;
 
    // Build prefix sums: prefix[i] = sum of nums[0..i-1]
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
 
    let ans = Infinity; // track the minimum subarray length found
 
    // Try every pair of left endpoint l and right endpoint r
    for (let l = 0; l <= n; l++) {
        for (let r = l + 1; r <= n; r++) {
            // Sum of subarray nums[l..r-1] is prefix[r] - prefix[l]
            if (prefix[r] - prefix[l] >= k) {
                ans = Math.min(ans, r - l); // r - l is the subarray length
            }
        }
    }
 
    // If no valid subarray was found, return -1
    return ans === Infinity ? -1 : ans;
}

Optimal: Prefix Sum + Monotonic Deque — O(n) Time, O(n) Space#

This is the solution interviewers expect. Each index is pushed and popped from the deque at most once, giving true O(n) performance.

Python:

from collections import deque
from typing import List
 
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
 
        # Step 1: Build prefix sum array of size n+1
        # P[i] = nums[0] + nums[1] + ... + nums[i-1]
        # Sum of subarray nums[l..r-1] = P[r] - P[l]
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
 
        # Monotonic deque stores INDICES into the prefix array.
        # Invariant: prefix values at those indices are strictly increasing
        # (from front to back). This means the deque stores the "best"
        # left-endpoint candidates for future right endpoints.
        dq = deque()
 
        ans = float('inf')  # will hold the minimum valid subarray length
 
        # Step 2: Process each index i from 0 to n (inclusive)
        for i in range(n + 1):
 
            # --- Front-pop phase: harvest valid subarrays ---
            # If prefix[i] - prefix[dq[0]] >= k, then the subarray
            # from index dq[0] to i-1 has sum >= k. Record its length
            # and pop dq[0] — it cannot give a shorter subarray for any
            # future i' > i, so it's safe to discard.
            while dq and prefix[i] - prefix[dq[0]] >= k:
                ans = min(ans, i - dq.popleft())
 
            # --- Back-pop phase: maintain the monotone invariant ---
            # If prefix[dq[-1]] >= prefix[i], discard dq[-1].
            # Reason: dq[-1] came before i, so using i as a left endpoint
            # gives both a smaller prefix[l] (larger potential difference)
            # AND a shorter subarray length. dq[-1] is strictly dominated.
            while dq and prefix[dq[-1]] >= prefix[i]:
                dq.pop()
 
            # Push i as a new left-endpoint candidate
            dq.append(i)
 
        # If no valid subarray was found, return -1
        return ans if ans != float('inf') else -1

JavaScript:

function shortestSubarray(nums, k) {
    const n = nums.length;
 
    // Step 1: Build prefix sum array of size n+1
    // prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
    // Sum of subarray nums[l..r-1] = prefix[r] - prefix[l]
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
 
    // Monotonic deque: stores indices into the prefix array.
    // The prefix values at stored indices are strictly increasing
    // front-to-back (i.e., the deque is monotonically increasing in value).
    // We simulate a deque with an array and two pointers for O(1) operations.
    const dq = [];
    let head = 0; // points to the front of the active deque region
 
    let ans = Infinity; // will hold the minimum valid subarray length
 
    // Step 2: Process each index i from 0 to n (inclusive)
    for (let i = 0; i <= n; i++) {
 
        // --- Front-pop phase: harvest valid subarrays ---
        // While the front of the deque gives a prefix difference >= k,
        // we found a valid subarray. Record its length and discard the
        // front (it cannot contribute to a shorter answer in the future).
        while (head < dq.length && prefix[i] - prefix[dq[head]] >= k) {
            ans = Math.min(ans, i - dq[head]);
            head++; // pop from front
        }
 
        // --- Back-pop phase: maintain the monotone invariant ---
        // Discard any back indices whose prefix value >= prefix[i].
        // Index i is a strictly better left-endpoint candidate than those:
        // smaller prefix value (larger potential sum difference) AND later
        // index (shorter resulting subarray). They are dominated.
        while (head < dq.length && prefix[dq[dq.length - 1]] >= prefix[i]) {
            dq.pop(); // pop from back
        }
 
        // Push i as a new left-endpoint candidate
        dq.push(i);
    }
 
    // If no valid subarray was found, return -1
    return ans === Infinity ? -1 : ans;
}

Complexity Analysis#

Why O(n) for the deque approach? The outer loop runs n + 1 times. Each of the n + 1 indices is pushed onto the deque exactly once. Each index is also popped at most once (either from the front during the harvesting phase, or from the back during the cleanup phase). So the total number of push and pop operations across the entire algorithm is at most 2(n + 1) — O(n) total. The while loops do not add extra passes; they just amortize over previous pushes.

Space: The prefix array is always O(n). The deque holds at most n + 1 indices at any time, so also O(n).

Follow-up Questions#

1. Minimum Size Subarray Sum — LeetCode 209 (Medium) — No Negatives#

"What if all numbers are guaranteed to be positive?"

When all elements are positive, the standard two-pointer sliding window works perfectly. Maintain a running window sum. If the sum is >= k, shrink from the left (since shrinking can only decrease the sum, and we want the shortest such window). This is O(n) time and O(1) space — strictly better than the deque approach in this special case.

The key lesson: always check whether the input has negatives. If it does not, use the simpler approach. If it might, escalate to the deque.

2. Number of Subarrays with Bounded Maximum — LeetCode 795 (Medium)#

"Count subarrays where the maximum element is between L and R."

This uses a different sliding window variant but similarly relies on prefix counts and careful boundary management. Good follow-up for practicing the "count subarrays satisfying a condition" family.

3. Sliding Window Maximum — LeetCode 239 (Hard)#

"Given a sliding window of size k, find the maximum element in each window position."

This is the direct sibling of our deque approach. Instead of a monotonically increasing deque tracking prefix sums, you maintain a monotonically decreasing deque tracking array values. The structural logic (pop from front when out of window, pop from back when dominated) is identical. Mastering one gives the other almost for free.

4. Shortest Subarray with Sum at Most K#

"Instead of at least K, find the shortest subarray with sum at most K."

This is a natural inversion and requires a similar but adapted approach. With a monotonic deque on prefix sums, you look for pairs where P[r] - P[l] <= k and you want to minimize r - l. The deque maintenance logic flips direction. This is a good self-check problem after mastering the original.

5. Maximum Sum of Two Non-Overlapping Subarrays — LeetCode 1031 (Medium)#

"Find two non-overlapping subarrays with specified lengths whose combined sum is maximum."

This extends the prefix sum idea into combining multiple subarray queries. The prefix sum array is precomputed once, then the problem reduces to efficient range queries — a natural extension of today's technique.

This Pattern Solves#

The monotonic deque on prefix sums pattern is one of the most powerful tools in competitive programming. Once you understand the structure here, the following problems become approachable:

The common thread: you have a function over pairs of indices in a prefix array, you want to find an optimal pair, and a monotonic deque lets you avoid checking all O(n^2) pairs by discarding dominated candidates eagerly.

Key Takeaways#

• Negative numbers break the classic two-pointer sliding window — you cannot guarantee that shrinking the window decreases the sum, so a standard shrink loop is incorrect.
• The correct approach: compute prefix sums P, then find the minimum r - l such that P[r] - P[l] >= k using a monotonically increasing deque of indices into P.
• Front-pop (harvest): while P[r] - P[deque.front()] >= k, record the length and pop the front — it can only give longer subarrays to future right endpoints.
• Back-pop (dominance): while P[r] <= P[deque.back()], pop the back — r is a strictly better left-endpoint candidate for all future right endpoints.
• O(n) time (each index pushed and popped at most once), O(n) space for the prefix array and deque.
• The prefix array has length n+1 (P[0] = 0), so subarray nums[l..r-1] has sum P[r] - P[l].
• This problem appears frequently in Google and Amazon hard rounds as a test of whether candidates know when two-pointer fails and what to use instead.