Given positive integers and a target, find the shortest contiguous subarray whose sum is at least the target. Return its length, or 0 if no such subarray exists.
DSA Animator › DSA Revision › Arrays › Minimum Size Subarray Sum
Remember: with positive numbers, expand until valid, then shrink while still valid. Record the answer inside the shrinking loop. The video solves Minimum Size Subarray Sum (LeetCode 209, Medium) with the Sliding Window pattern from the Arrays topic, and you can replay every step in the interactive Minimum Size Subarray Sum animation.
Given positive integers and a target, find the shortest contiguous subarray whose sum is at least the target. Return its length, or 0 if no such subarray exists.
For 2, 3, 1, 2, 4, 3 with target 7, the answer is 2. The subarray 4, 3 adds up to exactly 7.
Trying every start and end is O of n squared. Because every number is positive, growing a window only increases its sum, and shrinking only decreases it.
Expand the window to the right until its sum reaches the target. Then shrink it from the left as far as possible, while it still reaches the target. Every time the window is valid, record its length.
Adding 2, 3, 1 and 2 reaches a sum of 8 at indexes 0 to 3, length 4. Removing the 2 on the left drops the sum to 6, so we expand again. Adding 4 gives indexes 1 to 4 with sum 10, still length 4, and removing 3 leaves sum 7, at length 3. Removing 1 leaves 6, so we expand with 3: indexes 3 to 5 sum to 9, length 3. Removing 2 leaves 4 and 3, which is exactly 7, at length 2. Nothing shorter appears, so the answer is 2.
In code, add each new number to the running sum. While the sum is at least the target, update the best length, then subtract the left number and move left forward. If best was never set, return 0. Each number enters and leaves once, so it's O of n time and O of 1 space.
Remember: with positive numbers, expand until valid, then shrink while still valid. Record the answer inside the shrinking loop.