LeetCode 862 - Shortest Subarray with Sum at Least K

The problem asks us to find the length of the shortest contiguous subarray whose sum is at least k. We are given an integer array nums, which may contain both positive and negative numbers, and an integer k.

leetcodehardarraybinary-searchqueuesliding-windowheap-(priority-queue)prefix-summonotonic-queue

LeetCode Problem 862

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Queue, Sliding Window, Heap (Priority Queue), Prefix Sum, Monotonic Queue

Solution

Problem Understanding

The problem asks us to find the length of the shortest contiguous subarray whose sum is at least k.

We are given an integer array nums, which may contain both positive and negative numbers, and an integer k. We must return the minimum length among all non-empty contiguous subarrays whose sum is greater than or equal to k. If no such subarray exists, we return -1.

The key detail is that the subarray must be contiguous. We are not allowed to skip elements.

For example, if:

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

the entire array sums to 3, so the answer is 3.

The presence of negative numbers is what makes this problem difficult. If all numbers were positive, a standard sliding window would work because expanding the window would always increase the sum. With negative numbers, removing or adding elements can unpredictably increase or decrease the total, so a normal two pointer approach fails.

The constraints are large:

  • nums.length can be up to 100000
  • Values can be negative
  • k can be as large as 10^9

These constraints immediately rule out quadratic solutions. Any algorithm close to O(n^2) will time out.

Several important edge cases appear naturally:

  • No valid subarray exists
  • A single element itself is at least k
  • Negative values reduce prefix sums
  • Multiple overlapping candidate subarrays exist
  • Very large positive and negative values appear together

Because the array can contain negative numbers, we need a strategy that efficiently finds valid subarrays without checking every possible range.

Approaches

Brute Force Approach

The most direct solution is to check every possible subarray.

For every starting index i, we compute the sum of subarrays ending at every j >= i. Whenever the sum becomes at least k, we update the shortest length found.

This works because it explicitly evaluates every contiguous subarray, so it cannot miss the optimal answer.

However, there are O(n^2) subarrays. With n = 100000, this becomes far too slow.

Even using prefix sums to compute each subarray sum in O(1) time still leaves us with O(n^2) total subarrays.

Key Insight for the Optimal Solution

The crucial observation is that prefix sums allow us to transform the subarray condition.

Define:

prefix[i] = sum of first i elements

Then the sum of subarray [j, i) is:

prefix[i] - prefix[j]

We need:

prefix[i] - prefix[j] >= k

Rearranging:

prefix[j] <= prefix[i] - k

For every current prefix sum prefix[i], we want to find the earliest valid j that produces the shortest subarray.

The challenge is doing this efficiently.

The optimal solution uses a monotonic deque:

  • The deque stores indices of prefix sums
  • Prefix sums inside the deque are maintained in increasing order
  • If a newer prefix sum is smaller than an older one, the older one is useless and can be removed
  • While the current prefix sum forms a valid subarray with the front of the deque, we update the answer and pop from the front

This guarantees linear time complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every possible subarray
Optimal O(n) O(n) Uses prefix sums with a monotonic deque

Algorithm Walkthrough

Step 1: Build Prefix Sums

We create a prefix sum array where:

prefix[i] = sum of nums[0:i]

The prefix array has length n + 1.

This allows any subarray sum to be computed in constant time.

Step 2: Initialize the Monotonic Deque

We use a deque to store indices of prefix sums.

The deque maintains increasing prefix sum values.

Why increasing order matters:

If we already have two indices:

i < j

and:

prefix[j] <= prefix[i]

then index i is never useful again.

Any future subarray using i would be longer and have a larger or equal prefix sum compared to using j.

So we remove dominated prefix sums.

Step 3: Iterate Through Prefix Sums

For every index i in the prefix array:

First Condition: Check Valid Subarrays

While:

prefix[i] - prefix[deque[0]] >= k

we found a valid subarray.

The subarray length is:

i - deque[0]

We update the answer and pop from the front.

Why pop?

Because once this index produces a valid subarray, any future subarray using the same starting point would only be longer.

Step 4: Maintain Monotonic Order

While the deque is not empty and:

prefix[i] <= prefix[deque[-1]]

we remove the back element.

The current prefix sum is better because:

  • it is smaller
  • it occurs later
  • it can potentially create shorter future subarrays

Step 5: Add Current Index

Append the current index to the deque.

Step 6: Return Result

If we never found a valid subarray, return -1.

Otherwise return the minimum length found.

Why it works

The deque always stores candidate starting indices in increasing order of prefix sums.

For each current prefix sum:

  • the front of the deque gives the earliest valid subarray
  • removing larger prefix sums from the back guarantees we never keep dominated candidates
  • each index enters and leaves the deque at most once

Because we process prefix sums in order and always maintain the best possible candidates, the algorithm correctly finds the shortest valid subarray.

Python Solution

from collections import deque
from typing import List

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)

        prefix = [0] * (n + 1)

        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        answer = n + 1
        mono_queue = deque()

        for i in range(n + 1):
            while mono_queue and prefix[i] - prefix[mono_queue[0]] >= k:
                answer = min(answer, i - mono_queue.popleft())

            while mono_queue and prefix[i] <= prefix[mono_queue[-1]]:
                mono_queue.pop()

            mono_queue.append(i)

        return answer if answer <= n else -1

The implementation begins by constructing the prefix sum array. The prefix array has one extra element so that subarrays starting at index 0 can be handled naturally.

The variable answer stores the shortest valid length found so far. It is initialized to n + 1, which acts as an impossible large value.

The deque stores indices into the prefix sum array, not the prefix sums themselves.

Inside the main loop, the first while loop checks whether the current prefix sum forms a valid subarray with the smallest prefix sum at the front of the deque. If it does, we update the answer and remove that index because any future subarray using it would be longer.

The second while loop maintains increasing prefix sums inside the deque. Any larger or equal prefix sum is removed because the current prefix sum is strictly better.

Finally, the current index is appended.

At the end, if answer was never updated, we return -1.

Go Solution

func shortestSubarray(nums []int, k int) int {
	n := len(nums)

	prefix := make([]int64, n+1)

	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + int64(nums[i])
	}

	answer := n + 1
	deque := make([]int, 0)

	for i := 0; i <= n; i++ {
		for len(deque) > 0 &&
			prefix[i]-prefix[deque[0]] >= int64(k) {

			length := i - deque[0]

			if length < answer {
				answer = length
			}

			deque = deque[1:]
		}

		for len(deque) > 0 &&
			prefix[i] <= prefix[deque[len(deque)-1]] {

			deque = deque[:len(deque)-1]
		}

		deque = append(deque, i)
	}

	if answer == n+1 {
		return -1
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

One important difference is integer overflow handling. Since prefix sums can become large, the prefix array uses int64.

Go does not have a built in deque structure, so a slice is used instead. Removing from the front is done with:

deque = deque[1:]

and removing from the back uses slice truncation.

Otherwise, the algorithm remains identical.

Worked Examples

Example 1

nums = [1]
k = 1

Prefix sums:

[0, 1]
i prefix[i] Deque Before Action Answer
0 0 [] append 0 inf
1 1 [0] 1 - 0 >= 1, valid 1

Final answer:

1

Example 2

nums = [1, 2]
k = 4

Prefix sums:

[0, 1, 3]
i prefix[i] Deque Valid?
0 0 [0] no
1 1 [0,1] no
2 3 [0,1,2] no

No valid subarray exists.

Answer:

-1

Example 3

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

Prefix sums:

[0, 2, 1, 3]
i prefix[i] Deque Before Action Answer
0 0 [] append 0 inf
1 2 [0] append 1 inf
2 1 [0,1] pop 1 because 1 <= 2 inf
2 1 [0] append 2 inf
3 3 [0,2] 3 - 0 >= 3 3

Final answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index enters and leaves the deque at most once
Space O(n) Prefix sums and deque both require linear space

The algorithm is linear because every prefix index is appended to the deque once and removed at most once. No nested iteration over the array occurs. Even though there are while loops, the total number of deque operations across the entire execution is bounded by O(n).

Test Cases

from typing import List
from collections import deque

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)

        prefix = [0] * (n + 1)

        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        answer = n + 1
        mono_queue = deque()

        for i in range(n + 1):
            while mono_queue and prefix[i] - prefix[mono_queue[0]] >= k:
                answer = min(answer, i - mono_queue.popleft())

            while mono_queue and prefix[i] <= prefix[mono_queue[-1]]:
                mono_queue.pop()

            mono_queue.append(i)

        return answer if answer <= n else -1

sol = Solution()

assert sol.shortestSubarray([1], 1) == 1  # single element equals k
assert sol.shortestSubarray([1, 2], 4) == -1  # no valid subarray
assert sol.shortestSubarray([2, -1, 2], 3) == 3  # entire array needed

assert sol.shortestSubarray([5], 3) == 1  # single element greater than k
assert sol.shortestSubarray([-1, -2, -3], 1) == -1  # all negative numbers
assert sol.shortestSubarray([1, 2, 3, 4], 6) == 2  # shortest subarray in middle
assert sol.shortestSubarray([84, -37, 32, 40, 95], 167) == 3  # classic hard case
assert sol.shortestSubarray([17, 85, 93, -45, -21], 150) == 2  # negative values mixed
assert sol.shortestSubarray([1, -1, 5, -2, 3], 3) == 1  # single large positive
assert sol.shortestSubarray([2, 2, 2], 4) == 2  # multiple equal candidates
assert sol.shortestSubarray([100000], 100000) == 1  # upper value boundary
assert sol.shortestSubarray([1] * 1000, 500) == 500  # long uniform array
Test Why
[1], k=1 Simplest valid case
[1,2], k=4 No valid subarray
[2,-1,2], k=3 Entire array required
[5], k=3 Single element exceeds k
[-1,-2,-3], k=1 Impossible due to negatives
[1,2,3,4], k=6 Shortest valid range not at ends
[84,-37,32,40,95], k=167 Important monotonic queue case
[17,85,93,-45,-21], k=150 Mixed positives and negatives
[1,-1,5,-2,3], k=3 Best answer has length 1
[2,2,2], k=4 Multiple optimal windows
[100000], k=100000 Boundary value test
[1] * 1000, k=500 Stress test with large input

Edge Cases

No Valid Subarray Exists

An important edge case occurs when no contiguous subarray reaches sum k.

For example:

nums = [1, 2]
k = 10

A buggy implementation might incorrectly return a large default value or accidentally return 0.

This implementation initializes the answer to n + 1 and only updates it when a valid subarray is found. If the answer remains unchanged, the algorithm correctly returns -1.

Negative Numbers Break Standard Sliding Window Logic

Negative values are the main reason this problem is difficult.

For example:

nums = [2, -1, 2]

A normal sliding window relies on the assumption that expanding the window always increases the sum. That assumption fails here because adding -1 decreases the total.

The monotonic deque approach avoids this issue entirely by working with prefix sums instead of dynamically adjusting window boundaries.

Multiple Prefix Sums with Non Increasing Values

Consider:

prefix = [0, 5, 3]

The prefix sum 5 is useless once 3 appears later because:

  • 3 is smaller
  • it appears later
  • it produces shorter future subarrays

If we fail to remove dominated prefix sums, we may miss the optimal answer or waste time processing unnecessary candidates.

The second while loop ensures the deque always remains monotonic, guaranteeing correctness and linear performance.