Min Size Subarray Sum LeetCode 209

LeetCode 209 Minimum Size Subarray Sum asks you to find the minimal length contiguous subarray of a given array of positive integers whose sum is greater than or equal to a target value. If no such subarray exists, return 0.

Because all elements are positive, adding more elements always increases the sum and removing elements always decreases it. This monotonic property is precisely what makes the sliding window technique applicable and guarantees a correct solution without backtracking.

The follow-up challenge asks for an O(n log n) solution using prefix sums combined with binary search — useful for understanding the problem from multiple angles, though the sliding window O(n) solution is the preferred interview answer.

The variable sliding window approach maintains a window defined by left and right pointers. The right pointer expands the window one element at a time, adding each element to the running sum. When the sum reaches or exceeds the target, the window is valid and we record its length.

Once the window is valid, we shrink from the left to minimize the length. We subtract nums[left] from the sum and advance left, then check whether the window is still valid. We keep shrinking as long as the sum remains >= target, recording the minimum length at each step.

This two-pointer movement guarantees each element is added exactly once and removed at most once, giving O(n) overall time. The window dynamically resizes — it is not a fixed-size window, which is why this variant is called a variable or dynamic sliding window.

Initialize left = 0, currentSum = 0, and minLen = Infinity before the main loop. Iterate right from 0 to n-1, adding nums[right] to currentSum at each step. Whenever currentSum >= target, enter an inner shrink loop.

Inside the shrink loop, update minLen = min(minLen, right - left + 1), subtract nums[left] from currentSum, and increment left. Continue shrinking while currentSum >= target. After the outer loop completes, return minLen if it is still finite, otherwise return 0.

The algorithm runs in O(n) time because each index is visited at most twice — once when right advances over it and once when left advances past it. Space complexity is O(1) since only a constant number of variables are maintained regardless of input size.

A common mistake is using an if statement instead of a while loop for the shrink step. The if version only shrinks the window once when the sum is >= target, then moves on. This misses cases where the window can be shrunk multiple times and still satisfy the constraint.

Consider target=4 and nums=[1, 1, 5, 1]. When right reaches index 2 (value 5), the sum is 7 >= 4. An if statement records length 3 and shrinks once to [1, 5] with sum 6 >= 4 — but stops there and misses the valid window [5] of length 1. The while loop keeps shrinking and records length 1.

Each iteration of the inner while loop represents a candidate minimum. A single large element might satisfy the target all by itself, but the if version can only discover this if no smaller elements preceded it in the current window. The while loop explores all possible left boundaries for the current right.

Use target = 7 and nums = [2, 3, 1, 2, 4, 3]. Start with left = 0, currentSum = 0, minLen = Infinity. Expand right across each element, updating the sum and shrinking whenever the constraint is satisfied.

At right=3 (value 2), sum = 2+3+1+2 = 8 >= 7, so minLen = 4. Shrink: remove 2 (left=1), sum = 6 < 7, stop. At right=4 (value 4), sum = 3+1+2+4 = 10 >= 7, minLen = min(4, 4) = 4. Shrink: remove 3 (left=2), sum=7>=7, minLen=min(4,3)=3. Shrink: remove 1 (left=3), sum=6<7, stop.

At right=5 (value 3), sum = 2+4+3 = 9 >= 7, minLen = min(3, 3) = 3. Shrink: remove 2 (left=4), sum=7>=7, minLen=min(3,2)=2. Shrink: remove 4 (left=5), sum=3<7, stop. The answer is 2 (the subarray [4, 3]).

In Python: initialize left = 0, total = 0, res = float("inf"). For right in range(len(nums)): total += nums[right]. While total >= target: res = min(res, right - left + 1); total -= nums[left]; left += 1. Return res if res != float("inf") else 0. One for loop, one nested while loop, O(n) time, O(1) space.

In Java: int left = 0, total = 0, res = Integer.MAX_VALUE. For (int right = 0; right < nums.length; right++): total += nums[right]. While (total >= target): res = Math.min(res, right - left + 1); total -= nums[left++]. Return res == Integer.MAX_VALUE ? 0 : res. Same structure, same complexity.

Each element is added exactly once (by right) and removed at most once (by left), confirming O(n) amortized time. There are no nested loops with overlapping iterations — the inner while loop advances left, which is monotonically increasing and bounded by right.

Minimum Size Subarray Sum is the prototypical variable window problem. Max Consecutive Ones III (LeetCode 1004) uses the same expand-then-shrink pattern: expand while flips <= k, shrink when flips exceed k. Longest Repeating Character Replacement (LeetCode 424) similarly expands greedily and shrinks only when the window becomes invalid.

Minimum Window Substring (LeetCode 76) is the natural generalization: instead of a sum constraint, the validity check is whether the window contains all required characters. The outer loop still expands right and the inner loop still shrinks left — the while condition is more complex but the structure is identical.

For interview preparation, master this pattern with LeetCode 209 first, then apply it to 1004, 424, and 76 in that order. Each subsequent problem adds one layer of complexity while keeping the two-pointer skeleton intact, making it easy to recognize and apply the pattern under time pressure.