FAANG · LeetCode #862

Shortest Subarray with Sum at Least K — three-stage drill

1The ProblemHard

Shortest Subarray with Sum at Least K

Shortest subarray with sum ≥ k — but values can be negative.

Examples

[3,-2,5], k=4→ 1[1,2], k=4→ -1

constraintValues may be negative.

2The PatternTIME O(n) · SPACE O(n)

Monotonic Deque

A deque kept sorted by popping the back — the front is always the best candidate.

Problems using this pattern

3The SolutionRESULT → 1

Step through it

i=0 (P=0): deque empty → push index 0

Step 1 / 8

Python▎pop front (valid) · pop back (monotonic)

1from collections import deque
2def shortestSubarray(nums, k):
3    n, P = len(nums), [0]
4    for x in nums:
5        P.append(P[-1] + x)
6    best, dq = n + 1, deque()
7    for i in range(n + 1):
8        while dq and P[i] - P[dq[0]] >= k:
9            best = min(best, i - dq.popleft())
10        while dq and P[dq[-1]] >= P[i]:
11            dq.pop()
12        dq.append(i)
13    return best if best <= n else -1

why it worksThe #209 sliding window breaks here because negatives can lower the sum, so the window can't safely shrink. Working on prefix sums P (sum of (j,i] is P[i]−P[j]), a monotonic deque keeps candidate starts j with increasing P[j]: the front gives the shortest valid window, and a smaller P[i] evicts larger ones from the back.

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Shortest Subarray with Sum at Least K — three-stage drill