079. Shortest Subarray Sum At Least K with Negatives

Why this mechanism works

Negative values break ordinary window monotonicity, so move to prefix sums. A later prefix no greater than an earlier prefix dominates it as a future start: it yields at least as much sum with a shorter interval. Keep increasing prefix values in a deque. Qualifying starts are removed from the front after recording their shortest opportunity.

State and boundaries

prefix boundaries in candidates increase in both index and prefix value. best is the shortest qualifying interval already recorded.

Protocol

1. Build leading-zero prefix sums.
2. For each boundary first remove qualifying front starts while updating best.
3. Remove back starts with prefix>=current prefix.
4. Append the current boundary only after querying.
5. Return -1 if no candidate was recorded.

Visualization

nums [2,-1,2], prefixes 0,2,1,3
prefix 1 dominates earlier prefix 2
current 3 minus start 0 reaches k=3
length 3

Python implementation

from collections import deque

def shortest_sum_at_least(nums, k):
    prefix = [0]
    for value in nums:
        prefix.append(prefix[-1] + value)
    candidates = deque()
    best = len(nums) + 1
    for right, total in enumerate(prefix):
        while candidates and total - prefix[candidates[0]] >= k:
            best = min(best, right - candidates.popleft())
        while candidates and prefix[candidates[-1]] >= total:
            candidates.pop()
        candidates.append(right)
    return -1 if best > len(nums) else best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 shortest_sum_at_least: prefix = [0]
nums=[2, -1, 2]; k=3; prefix=[0]

L5 shortest_sum_at_least: for value in nums:
nums=[2, -1, 2]; k=3; prefix=[0]; value=2

L6 shortest_sum_at_least: prefix.append(prefix[-1] + value)
nums=[2, -1, 2]; k=3; prefix=[0, 2]; value=2

L5 shortest_sum_at_least: for value in nums:
nums=[2, -1, 2]; k=3; prefix=[0, 2]; value=-1

L6 shortest_sum_at_least: prefix.append(prefix[-1] + value)
nums=[2, -1, 2]; k=3; prefix=[0, 2, 1]; value=-1

L5 shortest_sum_at_least: for value in nums:
nums=[2, -1, 2]; k=3; prefix=[0, 2, 1]; value=2

L6 shortest_sum_at_least: prefix.append(prefix[-1] + value)
nums=[2, -1, 2]; k=3; prefix=[0, 2, 1, 3]; value=2

L7 shortest_sum_at_least: candidates = deque()
nums=[2, -1, 2]; k=3; prefix=[0, 2, 1, 3]; value=2; candidates=deque([])

... 7 intermediate state changes omitted ...

L14 shortest_sum_at_least: candidates.append(right)
nums=[2, -1, 2]; k=3; prefix=[0, 2, 1, 3]; value=2; candidates=deque([0, 2]); best=4; right=2; total=1

L9 shortest_sum_at_least: for right, total in enumerate(prefix):
nums=[2, -1, 2]; k=3; prefix=[0, 2, 1, 3]; value=2; candidates=deque([0, 2]); best=4; right=3; total=3

L11 shortest_sum_at_least: best = min(best, right - candidates.popleft())
nums=[2, -1, 2]; k=3; prefix=[0, 2, 1, 3]; value=2; candidates=deque([2]); best=3; right=3; total=3

L14 shortest_sum_at_least: candidates.append(right)
nums=[2, -1, 2]; k=3; prefix=[0, 2, 1, 3]; value=2; candidates=deque([2, 3]); best=3; right=3; total=3

L4 shortest_sum_at_least: prefix = [0]
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0]

L5 shortest_sum_at_least: for value in nums:
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0]; value=84

L6 shortest_sum_at_least: prefix.append(prefix[-1] + value)
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0, 84]; value=84

L5 shortest_sum_at_least: for value in nums:
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0, 84]; value=-37

L6 shortest_sum_at_least: prefix.append(prefix[-1] + value)
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0, 84, 47]; value=-37

L5 shortest_sum_at_least: for value in nums:
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0, 84, 47]; value=32

L6 shortest_sum_at_least: prefix.append(prefix[-1] + value)
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0, 84, 47, 79]; value=32

L5 shortest_sum_at_least: for value in nums:
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0, 84, 47, 79]; value=40

... 16 intermediate state changes omitted ...

L9 shortest_sum_at_least: for right, total in enumerate(prefix):
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0, 84, 47, 79, 119, 214]; value=95; candidates=deque([0, 2, 3, 4]); best=6; right=5; total=214

L11 shortest_sum_at_least: best = min(best, right - candidates.popleft())
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0, 84, 47, 79, 119, 214]; value=95; candidates=deque([2, 3, 4]); best=5; right=5; total=214

L11 shortest_sum_at_least: best = min(best, right - candidates.popleft())
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0, 84, 47, 79, 119, 214]; value=95; candidates=deque([3, 4]); best=3; right=5; total=214

L14 shortest_sum_at_least: candidates.append(right)
nums=[84, -37, 32, 40, 95]; k=167; prefix=[0, 84, 47, 79, 119, 214]; value=95; candidates=deque([3, 4, 5]); best=3; right=5; total=214

Why the solution is correct

A front start that qualifies cannot yield a shorter interval at a later end, so it is safely finalized. A back start dominated by a later lower prefix can never outperform its replacement at a future end. Querying before appending excludes empty intervals and preserves correctness even for nonpositive k.

Time and space

O(n) time and O(n) space; every prefix boundary is inserted and removed at most once.

Common mistakes

Applying the positive-only shrink rule fails with negative values. Appending the current boundary before testing can admit an empty interval.

Reasoning card

Transfer exercise

Explain each deque removal as a distinct proof: completed opportunity at the front and future dominance at the back.