Shortest Subarray with Sum at Least K: Prefix Sums Meet a Monotonic Deque

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 no such subarray exists, return -1.

nums = [2, -1, 2], k = 3  ->  3
nums = [1],        k = 1  ->  1
nums = [1, 2],     k = 4  -> -1

This is LeetCode 862: Shortest Subarray with Sum at Least K, a hard problem that combines prefix sums with a monotonic deque. If you have solved Minimum Size Subarray Sum (the version with only positive numbers), this problem adds a twist: nums can contain negative values, which breaks the standard sliding window.

Why this problem matters

The positive-only version of this problem is a classic sliding window exercise. You expand the right pointer until the sum meets the target, then shrink the left pointer while the sum stays valid. That works because adding elements can only increase the sum and removing them can only decrease it.

Negative numbers destroy that monotonic property. When you expand the window, the sum might decrease. When you shrink, it might increase (if you remove a negative element). A standard two-pointer approach has no way to know when to stop shrinking or when to resume expanding.

This problem forces you to reach for a more powerful tool: the monotonic deque. The deque maintains a set of candidate start positions, pruning any that can never lead to an optimal answer. The result is an O(n) algorithm that handles negative numbers gracefully. Understanding this technique gives you a reusable pattern for problems where sliding window breaks down but you still need to find optimal subarrays efficiently.

The brute force approach

def shortestSubarray(nums, k):
    n = len(nums)
    best = float("inf")
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]
            if total >= k:
                best = min(best, j - i + 1)
                break
    return best if best != float("inf") else -1

This checks every possible subarray starting position and expands until the sum reaches k. The break helps in some cases, but with negative numbers the sum can dip below k and then rise above it again later, so the break is actually incorrect for the general case. Even without the break, the approach is O(n^2), which is too slow for arrays up to length 100,000.

The key insight: monotonic deque over prefix sums

The core idea has two parts.

First, reframe the problem using prefix sums. If prefix[j] - prefix[i] >= k for some i < j, then the subarray from index i to index j-1 has sum at least k, and its length is j - i. You want to minimize j - i.

Second, use a deque (double-ended queue) to efficiently track which start indices are worth considering. The deque stores indices in a way that their prefix sums are strictly increasing from front to back. This gives you two powerful pruning rules:

1. Pop from the front when prefix[j] - prefix[deque_front] >= k. You have found a valid subarray. Record its length, then remove that front index because no future j could produce a shorter subarray starting from the same index (future j values are larger, making j - i larger).

2. Pop from the back when prefix[j] <= prefix[deque_back]. If the new prefix sum is smaller than or equal to the one at the back, the back index is useless. Any future position that could form a valid subarray with the back could also form a shorter one with j (because j is farther right and has a smaller or equal prefix sum).

Walking through it step by step

Take nums = [2, -1, 2, 3, -2] with k = 5. The prefix sum array is [0, 2, 1, 3, 6, 4]. The deque starts empty, and we scan through the prefix sums from left to right, maintaining the monotonic invariant at each step.

The algorithm discovers that the subarray from index 2 to index 3 (values [2, 3]) sums to 5 with length 2. This corresponds to prefix[4] - prefix[2] = 6 - 1 = 5 >= k. No shorter valid subarray exists, so the answer is 2.

The optimal solution

from collections import deque

def shortestSubarray(nums, k):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    dq = deque()
    best = float("inf")

    for j in range(n + 1):
        while dq and prefix[j] - prefix[dq[0]] >= k:
            best = min(best, j - dq.popleft())
        while dq and prefix[j] <= prefix[dq[-1]]:
            dq.pop()
        dq.append(j)

    return best if best != float("inf") else -1

The function builds a prefix sum array of length n + 1, where prefix[0] = 0. It then scans through every index j from 0 to n. At each step, it pops from the front of the deque while the difference between prefix[j] and the prefix sum at the front index meets the threshold k. Each pop records a candidate answer. Then it pops from the back while the current prefix sum is no larger than the back's prefix sum, maintaining the monotonic property. Finally it pushes j onto the deque.

Every index enters the deque exactly once and leaves at most once, so the total work across all iterations is O(n).

Complexity analysis

Time: O(n). Building the prefix sum array takes O(n). Each index is pushed onto the deque once and popped at most once, so the deque operations contribute O(n) total work across all iterations of the outer loop.

Space: O(n). The prefix sum array uses O(n + 1) space, and the deque holds at most n + 1 indices. Both are linear in the input size.

Building blocks

1. Prefix sums for subarray queries

The prefix sum array transforms a subarray sum question into a difference question: "find pairs (i, j) where prefix[j] - prefix[i] >= k and j - i is minimized." This reframing decouples the sum calculation from the search, letting you focus on efficiently finding the best pair.

This same transformation powers Subarray Sum Equals K (using a hash map instead of a deque) and Continuous Subarray Sum (checking divisibility). The pattern is always the same: convert cumulative sums into a lookup or comparison problem.

2. Monotonic deque for sliding window optimization

The deque maintains a window of candidate start indices where prefix sums increase from front to back. The front-pop rule exploits the fact that once a start index produces a valid answer at position j, it can never produce a shorter answer at any later position. The back-pop rule exploits the fact that a later index with a smaller prefix sum dominates an earlier index with a larger prefix sum.

This monotonic deque technique also appears in Sliding Window Maximum, where the deque tracks maximum values instead of prefix sums. The structural pattern is identical: maintain a monotonic invariant by popping from both ends, ensuring O(n) total operations.

Edge cases

• All positive numbers: The algorithm works correctly, though a simpler sliding window would also suffice. The deque front-pop handles the shrinking automatically.
• All negative numbers: No subarray can have a positive sum (assuming k > 0). The prefix sums are strictly decreasing, so the front-pop condition never triggers. The function returns -1.
• Single element equal to k: prefix[1] - prefix[0] = nums[0] >= k. The deque pops the front immediately, giving length 1.
• k is very large: If no subarray sums to at least k, best stays at infinity and the function returns -1.
• Array with zeros: Zeros do not change the prefix sum. They lengthen subarrays without adding to the sum, so they never help. The deque handles them naturally.
• Large negative followed by large positive: For example, nums = [-100, 200] with k = 100. The prefix sums are [0, -100, 100]. At j = 2, prefix[2] - prefix[1] = 100 - (-100) = 200 >= 100, giving length 1. The back-pop rule ensures index 0 (prefix 0) is removed because prefix[1] = -100 is smaller and closer.

Common mistakes

1. Using a standard sliding window. With negative numbers, expanding the window can decrease the sum. Two pointers require the sum to move monotonically with the window boundaries, which does not hold here. You need the deque to handle non-monotonic prefix sums.

2. Forgetting to pop from the back. Without the back-pop step, the deque is not monotonic, and the front-pop step might miss shorter valid subarrays. Both pruning rules are essential for correctness and efficiency.

3. Using prefix[j] < prefix[dq[-1]] instead of prefix[j] <= prefix[dq[-1]]. If two indices have equal prefix sums, the later one is strictly better (it can produce shorter subarrays with future positions). You must pop on equality too.

4. Off-by-one in prefix sum indexing. The prefix sum array has length n + 1, with prefix[0] = 0. Forgetting the leading zero means you miss subarrays that start from the beginning of nums.

5. Not returning -1 when no valid subarray exists. Always check whether best was updated before returning it.

From understanding to recall

The monotonic deque pattern is powerful but has several moving parts: the prefix sum construction, the front-pop for harvesting valid answers, and the back-pop for maintaining monotonicity. In an interview, it is easy to forget one of these steps or mix up the comparison directions.

Spaced repetition helps you internalize these details by having you reconstruct the solution at increasing intervals. The first review cements the two-rule structure of the deque. The second review locks in the prefix sum indexing. By the third or fourth session, the entire algorithm flows from memory. You stop re-deriving the logic under pressure and start executing it directly.

This problem sits at the intersection of about 60 building blocks in the CodeBricks library, including prefix sums, monotonic data structures, and deque manipulation. Each building block reinforces the others, so practicing this problem also strengthens your skills on related problems like Sliding Window Maximum and Subarray Sum Equals K.

Related posts

• Subarray Sum Equals K - Same prefix sum idea but uses a hash map for exact equality instead of a deque for minimum length
• Minimum Size Subarray Sum - The positive-only version solvable with a standard sliding window
• Sliding Window Maximum - Another monotonic deque problem, tracking max values in a fixed-size window

CodeBricks uses spaced repetition to help you internalize patterns like the monotonic deque. Instead of re-reading solutions, you practice writing them from scratch at increasing intervals. Each review strengthens the connection between "negative numbers break sliding window" and "reach for a deque over prefix sums." Over time, the pattern becomes automatic.