text
Initialize min_length to infinity
For i from 0 to length(nums) - 1:
    Initialize current_sum to 0
    For j from i to length(nums) - 1:
        current_sum += nums[j]
        If current_sum >= target:
            min_length = min(min_length, j - i + 1)
            Break (since extending j further only increases length)
Return min_length (or 0 if unchanged)

Time Complexity Analysis: The time complexity is $O(N^2)$, where $N$ is the number of elements in nums. In the worst case, for every starting position, we iterate through the rest of the array.

Why it fails: The problem constraints state that nums.length can be up to $10^5$. An $O(N^2)$ solution results in approximately $10^{10}$ operations, which far exceeds the typical limit of $10^8$ operations per second allowed by online judges. This leads to a Time Limit Exceeded (TLE) error.

Core Insight for Minimum Size Subarray Sum

The transition from the brute force approach to the optimal solution relies on the property that all numbers in the input array are positive.

Because the numbers are positive, adding an element to the subarray always increases the sum, and removing an element always decreases the sum. This monotonicity allows us to avoid recalculating sums from scratch.

Instead of resetting our starting point for every iteration, we can maintain a "window" defined by two pointers, left and right.

1. We expand the right pointer to include more elements until the window's sum meets the target.
2. Once the condition is met (sum >= target), the current window is a candidate solution.
3. To find the minimal length, we then try to shrink the window from the left as much as possible while keeping the sum $\ge$ target.

Visual Description: Imagine the array as a strip of tape. You unroll the tape to the right (increment right) to gather enough sum. Once you have enough, you roll up the left side of the tape (increment left) to make the strip as short as possible without dropping below the target sum. This caterpillar-like movement ensures we check all potential minimal windows in a single pass.

Execution Flow

Let's trace nums = [2, 3, 1, 2, 4, 3], target = 7.

1. Start: window_start = 0, window_end = 0, sum = 0, min_len = $\infty$.
2. Expand: Add 2 (sum=2). sum < 7.
3. Expand: Add 3 (sum=5). sum < 7.
4. Expand: Add 1 (sum=6). sum < 7.
5. Expand: Add 2 (sum=8). sum >= 7. Condition met.
   • Shrink: Record length 4 ([2,3,1,2]). Subtract 2 (sum=6). Increment window_start to 1.
   • sum < 7, stop shrinking.
6. Expand: Add 4 (sum=10). sum >= 7.
   • Shrink: Record length 4 ([3,1,2,4]). Subtract 3 (sum=7). Increment window_start to 2.
   • Shrink: Record length 3 ([1,2,4]). Subtract 1 (sum=6). Increment window_start to 3.
   • sum < 7, stop shrinking.
7. Expand: Add 3 (sum=9). sum >= 7.
   • Shrink: Record length 3 ([2,4,3]). Subtract 2 (sum=7). Increment window_start to 4.
   • Shrink: Record length 2 ([4,3]). Subtract 4 (sum=3). Increment window_start to 5.
   • sum < 7, stop shrinking.
8. End: window_end reaches end of array.
9. Result: Minimal length found was 2.

Proof of Correctness

The algorithm is correct because it implicitly considers all valid starting positions. For any window_end, the logic finds the largest window_start such that sum(nums[window_start...window_end]) >= target. Since elements are positive, any subarray ending at window_end starting before our calculated window_start would be valid but longer (suboptimal). Any subarray ending at window_end starting after our calculated window_start would have a sum less than target (invalid). Thus, for every ending position, we find the local optimal length. The global minimum of these local optimums is the correct answer.

Reference Implementation

C++ Solution for LeetCode 209

cpp
#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int minSubArrayLen(int target, std::vector<int>& nums) {
        int min_length = INT_MAX;
        int current_sum = 0;
        int window_start = 0;

        for (int window_end = 0; window_end < nums.size(); ++window_end) {
            current_sum += nums[window_end];

            // Shrink the window as small as possible while the sum is valid
            while (current_sum >= target) {
                min_length = std::min(min_length, window_end - window_start + 1);
                current_sum -= nums[window_start];
                window_start++;
            }
        }

        return (min_length == INT_MAX) ? 0 : min_length;
    }
};

Java Solution for LeetCode 209

java
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int currentSum = 0;
        int windowStart = 0;

        for (int windowEnd = 0; windowEnd < nums.length; windowEnd++) {
            currentSum += nums[windowEnd];

            // Shrink the window as small as possible while the sum is valid
            while (currentSum >= target) {
                minLength = Math.min(minLength, windowEnd - windowStart + 1);
                currentSum -= nums[windowStart];
                windowStart++;
            }
        }

        return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
    }
}

Python Solution for LeetCode 209

python
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        min_length = float('inf')
        current_sum = 0
        window_start = 0
        
        for window_end in range(len(nums)):
            current_sum += nums[window_end]
            
            # Shrink the window as small as possible while the sum is valid
            while current_sum >= target:
                min_length = min(min_length, window_end - window_start + 1)
                current_sum -= nums[window_start]
                window_start += 1
                
        return 0 if min_length == float('inf') else min_length