Shortest Window with Sum at Least Target

core

Implement min_window_len(a, target) where a holds only positive integers. Return the length of the shortest contiguous subarray whose sum is at least target, or -1 if no subarray reaches it.

Grow a window with r and shrink it with l. Because every element is positive, the sum only grows as r advances and only falls as l advances, so one pass works: add a[r], then shrink from the left for as long as the window still qualifies, recording the length before each shrink step. The shrink is a while, not an if, and that word is the whole drill: one new element on the right can pay for several steps of the left edge, and an if takes exactly one of them, leaves l short of where it belongs, and records a window longer than the true one. The fumble survives small hand-traces because tiny examples rarely let one element fund more than one shrink step.

Example: min_window_len({1, 1, 1, 100}, 100) returns 1. When r reaches the 100, the sum jumps to 103 and the while walks l all the way to the 100 itself, recording lengths 4, 3, 2, and finally 1. An if shrinks once, records 4, and never sees the answer.

Input format: each test in tests/*.in is laid out as:

Line 1: n target, the array length and the sum to reach.
Line 2: the n values, space-separated.

Test 02.in reads:

1 5
5

This is a one-element array {5} with target = 5: the single element already reaches the target, so the answer is 1.

Where you'll use it:

✦ Solution & editorial unlock with the pass.