← DSA Atlas
Dedicated problem page · #862

Shortest Subarray with Sum at Least K

HardSliding WindowMonotonic deque over prefix sumsPrefix sums with an increasing deque
Solve on LeetCode ↗
862
HardSliding WindowPrefix sums with an increasing dequeMonotonic deque over prefix sums

Shortest Subarray with Sum at Least K

Given an integer array nums (which may contain negatives) and an integer k, return the length of the shortest non-empty contiguous subarray whose sum is at least k. Return -1 if no such subarray exists.

Open official problem prompt ↗
In plain English

Find the fewest consecutive elements whose sum reaches at least k, even when negatives make simple windows fail.

Picture it like this

You are tracking a runner's cumulative distance at each second (prefix sums). To find the shortest time span covering at least k meters, you keep a shortlist of promising start moments, ordered so earlier-and-lower readings stay and any start that is both later-recorded and no lower is thrown out because it can never beat the one before it.

Example
Input
nums = [2, -1, 2], k = 3
Output
3
Why
The whole array sums to 2 + (-1) + 2 = 3 >= k, and no shorter subarray reaches 3, so the answer is its length 3.
Constraints
1 <= nums.length <= 10^5-10^5 <= nums[i] <= 10^51 <= k <= 10^9
Pattern lesson

See the pattern, then code

Monotonic deque over prefix sums
Recognition clue

A subarray-sum-at-least-k question with NEGATIVE numbers rules out the plain two-pointer window (sums are no longer monotonic). The fix is prefix sums plus a monotonic deque — a hallmark of shortest-subarray-with-negatives problems.

↗
Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. A subarray sum equals prefix[j] - prefix[i]. For a fixed right end j we want the smallest j - i where prefix[j] - prefix[i] >= k. Keep candidate left indices in a deque with increasing prefix values: pop from the front when a valid pair is found (it is the shortest for that j), and pop from the back any prefix >= the current one because it is both larger and further left, so useless.

New words, made simpleKnow these before the algorithm
Prefix sum
prefix[i] is the sum of the first i elements; a subarray sum is a difference of two prefixes.
Monotonic increasing deque
A deque of indices kept so their prefix values increase from front to back.
Dominated start
A start index whose prefix is >= a later index's prefix — larger and further left, hence never useful.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute force all subarrays

Quadratic; fails at n = 10^5.

Try every start and end, summing to test >= k.

Time O(n^2)Space O(1)
Two-pointer sliding window

Incorrect here: negatives break monotonicity, so shrinking logic is invalid.

Grow/shrink a window tracking its sum.

Time O(n)Space O(1)
Best choicePrefix sums + monotonic deque

Handles negatives correctly in linear time.

Store increasing prefix indices; for each end pop qualifying fronts and dominated backs.

Time O(n)Space O(n)
The rule we keep true

Invariant

The deque always holds indices whose prefix values strictly increase from front to back, and it contains every index that could still be the optimal left endpoint for some future right endpoint.

Why this is correct

Reasoning

Popping the front once cur - prefix[front] >= k is safe because for any later end j' > i, i - front < j' - front, so front could only give a longer window later; we have already recorded its best. Popping a back whose prefix >= cur is safe because cur is smaller and its index is larger, so it dominates the popped one for every future end. Each index is pushed and popped at most once, so total work is linear.

The algorithm in three movesSay these aloud before coding
1Build prefix sums of length n+1

prefix = [0,2,1,3]

2Iterate over each prefix index i with value cur

i=3 cur=3: 3-prefix[0]=3>=k -> ans=3, popleft

3While cur - prefix[front] >= k, record i - front and pop the front (that start can never give a shorter valid window later)

deque stays increasing: pushing 1 popped the larger prefix 2

4While prefix[back] >= cur, pop the back (dominated), then append i

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
21
12
33
1 · Readcur=0
2 · AskFront qualifies? Dominated back?
3 · Update statedq=[0]
4 · ResultJust seed the deque.
Key takeaway

Prefix array [0,2,1,3]; the pair prefix[3]-prefix[0]=3 gives the shortest qualifying window of length 3.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-8Prefix sums

    prefix[i+1] holds the sum of the first i+1 elements so any subarray sum is prefix[end]-prefix[start].

  2. 2
    Lines 12-13Harvest valid fronts

    While the current prefix minus the smallest stored prefix reaches k, record the length and discard that front for good.

  3. 3
    Lines 14-15Maintain monotonicity

    Drop back indices whose prefix is >= current, since they are dominated.

  4. 4
    Lines 16-17Append and finalize

    Add the current index; return the best length or -1 if none reached k.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single element already >= k gives length 1
  • All negatives (or sums never reach k) -> -1
  • k = 1 with a mix of signs
  • Large sums exceeding 32-bit (Python ints are unbounded, but the constraint spans 10^10)
!

Common beginner mistakes

  • Trying a plain two-pointer window and getting wrong answers because negatives make the sum non-monotonic
  • Popping the front with > instead of >= and thus missing exact-k windows
  • Forgetting to include prefix index 0 (subarrays starting at the very beginning)
  • Not popping dominated backs, which breaks the increasing invariant and the linear-time bound
Check your understanding

Why does the ordinary two-pointer sliding window fail on this problem but works for all-positive variants like problem 209?

More in Sliding Window

#3Longest Substring Without Repeating CharactersVariable-size sliding window with last-seen index#424Longest Repeating Character ReplacementVariable-size window constrained by replaceable slots#76Minimum Window SubstringShrinkable window covering a multiset requirement#30Substring with Concatenation of All WordsWord-aligned sliding window over fixed-length tokens#121Best Time to Buy and Sell StockRunning minimum with best forward difference#209Minimum Size Subarray SumShrinking window on a sum threshold