048. Shortest Positive Window Reaching Target

Why this mechanism works

Expansion can only raise the sum, and removing from the left can only lower it. Once a window qualifies, record it before shrinking, then continue shrinking while it still qualifies. This is the opposite commit timing from longest-valid windows: the current satisfying candidate must be saved before repair destroys it.

State and boundaries

total is the active window sum. best is the shortest satisfying window encountered, initialized to an impossible length n+1.

Protocol

1. Add the incoming positive value.
2. While total>=target record the current length.
3. Remove the left value and advance left.
4. Continue expansion after qualification is lost.
5. Return zero if best was never improved.

Visualization

[2,3,1,2] sum 8 -> record 4
remove 2 -> sum 6, stop
later [4,3] sum 7 -> record 2

Python implementation

def shortest_positive_window(nums, target):
    left = total = 0
    best = len(nums) + 1
    for right, value in enumerate(nums):
        total += value
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 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.

L2 shortest_positive_window: left = total = 0
nums=[2, 3, 1, 2, 4, 3]; target=7; left=0; total=0

L3 shortest_positive_window: best = len(nums) + 1
nums=[2, 3, 1, 2, 4, 3]; target=7; left=0; total=0; best=7

L4 shortest_positive_window: for right, value in enumerate(nums):
nums=[2, 3, 1, 2, 4, 3]; target=7; left=0; total=0; best=7; right=0; value=2

L5 shortest_positive_window: total += value
nums=[2, 3, 1, 2, 4, 3]; target=7; left=0; total=2; best=7; right=0; value=2

L4 shortest_positive_window: for right, value in enumerate(nums):
nums=[2, 3, 1, 2, 4, 3]; target=7; left=0; total=2; best=7; right=1; value=3

L5 shortest_positive_window: total += value
nums=[2, 3, 1, 2, 4, 3]; target=7; left=0; total=5; best=7; right=1; value=3

L4 shortest_positive_window: for right, value in enumerate(nums):
nums=[2, 3, 1, 2, 4, 3]; target=7; left=0; total=5; best=7; right=2; value=1

L5 shortest_positive_window: total += value
nums=[2, 3, 1, 2, 4, 3]; target=7; left=0; total=6; best=7; right=2; value=1

... 15 intermediate state changes omitted ...

L9 shortest_positive_window: left += 1
nums=[2, 3, 1, 2, 4, 3]; target=7; left=4; total=7; best=3; right=5; value=3

L7 shortest_positive_window: best = min(best, right - left + 1)
nums=[2, 3, 1, 2, 4, 3]; target=7; left=4; total=7; best=2; right=5; value=3

L8 shortest_positive_window: total -= nums[left]
nums=[2, 3, 1, 2, 4, 3]; target=7; left=4; total=3; best=2; right=5; value=3

L9 shortest_positive_window: left += 1
nums=[2, 3, 1, 2, 4, 3]; target=7; left=5; total=3; best=2; right=5; value=3

L2 shortest_positive_window: left = total = 0
nums=[1, 1]; target=3; left=0; total=0

L3 shortest_positive_window: best = len(nums) + 1
nums=[1, 1]; target=3; left=0; total=0; best=3

L4 shortest_positive_window: for right, value in enumerate(nums):
nums=[1, 1]; target=3; left=0; total=0; best=3; right=0; value=1

L5 shortest_positive_window: total += value
nums=[1, 1]; target=3; left=0; total=1; best=3; right=0; value=1

L4 shortest_positive_window: for right, value in enumerate(nums):
nums=[1, 1]; target=3; left=0; total=1; best=3; right=1; value=1

L5 shortest_positive_window: total += value
nums=[1, 1]; target=3; left=0; total=2; best=3; right=1; value=1

Why the solution is correct

For each right endpoint, repeated shrinking visits every relevant satisfying left boundary until the first failure. Further shrinking cannot restore qualification because values are positive. Hence the shortest satisfying suffix at each endpoint is recorded, including the global optimum.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Committing after subtraction can record an invalid window. Negative values invalidate the monotone shrink argument; kata 079 supplies a different structure.

Reasoning card

Transfer exercise

Construct a counterexample showing why this exact loop is not valid when negative values are allowed.