LeetCode · #209

Minimum Size Subarray Sum Solution

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is at least target.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #209

🏗️

Pattern

Sliding Window — shrink when valid

The word positive is what unlocks the sliding-window solution. When all numbers are positive, expanding the right end can only increase the sum, and shrinking the left end can only decrease it. That monotonic behavior lets us find the minimum valid window in linear time.

Example 1

 Input: target = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2 // [4,3] is the shortest contiguous subarray with sum ≥ 7 

Example 2

 Input: target = 4, nums = [1, 4, 4]
Output: 1 

Example 3

 Input: target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1]
Output: 0 // No contiguous subarray reaches the target 

Constraints

 • 1 ≤ target ≤ 10⁹ • 1 ≤ nums.length ≤ 10⁵ • 1 ≤ nums[i] ≤ 10⁴ 

Section Two · Approach 1

Brute Force — Expand from Every Start

For each starting index, keep extending the subarray to the right and maintain a running sum. As soon as the sum reaches target, record the length and stop extending from that start because any longer subarray would not be minimal.

Problem: Even with the early break, the worst case is still quadratic. For arrays like many small ones, we may scan almost the entire suffix for many starting positions. The sliding-window version reuses that work instead of restarting from every index.

Java — Expand from each start

 class Solution {
public int minSubArrayLen(int target, int[] nums) {
int best = Integer.MAX_VALUE;
for (int start = 0; start < nums.length; start++) {
int sum = 0;
for (int end = start; end < nums.length; end++) {
                sum += nums[end];
if (sum >= target) {
                    best = Math.min(best, end - start + 1);
break;
                }
            }
        }
return best == Integer.MAX_VALUE ? 0 : best;
    }
}

Python — Expand from each start

 class Solution:
def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        best = float('inf')
for start in range(len(nums)):
            total = 0 for end in range(start, len(nums)):
                total += nums[end]
if total >= target:
                    best = min(best, end - start + 1)
break return 0 if best == float('inf') else best

Metric	Value
Time	O(n²)
Space	O(1)

Section Three · Approach 2

Variable-Size Sliding Window — O(n)

Maintain a window [left, right] and its running sum. Expand right until the window becomes valid (sum ≥ target). Then shrink left as much as possible while staying valid, updating the minimum length each time. This is the classic shrink when valid pattern.

💡 Mental model: Think of filling a bucket to reach a target water level. The right pointer pours water in until the bucket is full enough. Then the left pointer drains from the other side to see how much excess can be removed while still meeting the target. The smallest bucket span that still stays full enough is the answer.

Algorithm

Step 1: Initialize left = 0, sum = 0, and best = ∞.
Step 2: For each right, add nums[right] into sum.
Step 3: While sum ≥ target, the window is valid — update best.
Step 4: Still inside that loop, subtract nums[left] and move left forward to search for a shorter valid window.
Step 5: If best was never updated, return 0.

🎯 Why positivity matters:

This technique works because every value is positive.
That means moving right can only increase the sum, and moving left can only decrease it.
If negatives were allowed, shrinking could increase the sum and the whole monotonic window idea would break.

Section Four · Trace

Visual Walkthrough

Trace through target = 7, nums = [2, 3, 1, 2, 4, 3]:

Expand until valid, then shrink to minimum

Section Five · Implementation

Code — Java & Python

Java — Variable-size sliding window

 class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int best = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
while (sum >= target) {
                best = Math.min(best, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
return best == Integer.MAX_VALUE ? 0 : best;
    }
}

Python — Variable-size sliding window

 class Solution:
def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        left = 0
total = 0
best = float('inf')
for right in range(len(nums)):
            total += nums[right]
while total >= target:
                best = min(best, right - left + 1)
                total -= nums[left]
                left += 1 return 0 if best == float('inf') else best

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Expand from each start	O(n²)	O(1)	Simple but repeatedly rescans suffixes
Sliding window ← optimal	O(n)	O(1)	Each element enters and leaves the window once

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
No valid subarray	`target=11, nums=[1,1,1,1]`	Must return 0, not infinity or array length.
Single element works	`target=4, nums=[4]`	Answer can be 1 immediately.
Whole array needed	`target=15, nums=[1,2,3,4,5]`	Best answer may be the entire array length.
Many small positives	`[1,1,1,1,1,...]`	Brute force degrades badly; sliding window stays linear.
Positive-only guarantee	`nums=[2,-1,2]`	This problem avoids negatives; otherwise this pattern is not reliable.

⚠ Common Mistake: Applying this exact sliding-window template when negative numbers are allowed. With negatives, expanding the window may decrease the sum, so the left/right monotonic logic no longer guarantees correctness.

← Back to Sliding Window problems

LearningTree

LC 209 · Minimum Size Subarray Sum — Solution & Explanation | DSA Guide