Leetcode 209. Minimum Size Subarray Sum

Let's understand what we're being asked to do. We have an array of positive integers like [2, 3, 1, 2, 4, 3] and a target sum like 7. We need to find the shortest contiguous subarray whose sum is at least 7.

Tracing through: subarray [2,3,1,2] has sum 8 (length 4), subarray [3,1,2,4] has sum 10 (length 4), subarray [4,3] has sum 7 (length 2). The shortest is [4,3] with length 2!

Important constraint: All numbers are positive integers. This isn't just random data - the positivity property is crucial!

Edge cases to consider: What if no subarray sums to at least the target? (return 0). What if the entire array's sum is less than target? What if a single element is already >= target? What if the array is empty?

The brute force approach checks every possible contiguous subarray. Use two nested loops: the outer loop picks the starting index, and the inner loop extends to each possible ending index, calculating the sum along the way. For each subarray whose sum is at least the target, track the minimum length found. This approach is straightforward but inefficient because it recalculates sums redundantly and doesn't exploit the positive integer property.

def min_subarray_len(target, nums):
    """
    Find the minimal length of a contiguous subarray whose sum >= target.
    Brute force approach: check all possible subarrays.
    """
    n = len(nums)
    min_length = float('inf')
    
    # Outer loop: pick starting index
    for start in range(n):
        current_sum = 0
        
        # Inner loop: extend to each possible ending index
        for end in range(start, n):
            # Add current element to sum
            current_sum += nums[end]
            
            # Check if current subarray sum meets target
            if current_sum >= target:
                # Update minimum length found
                current_length = end - start + 1
                min_length = min(min_length, current_length)
    
    # Return 0 if no valid subarray found
    return 0 if min_length == float('inf') else min_length

As we extend a subarray to the right by adding elements, the sum only increases (since all numbers are positive). As we shrink it from the left by removing elements, the sum only decreases.

This means once we find a valid subarray (sum >= target), we can try shrinking it from the left to find a shorter valid subarray, without needing to re-check all possibilities.

Because of the monotonic property (sum only grows when extending right, only shrinks when contracting left), we can use two pointers that each move in one direction only.

This transforms a problem that seems like it needs O(n²) time (checking all subarrays) into an O(n) solution where each element is visited at most twice (once by right pointer, once by left pointer).

Imagine you're measuring a rubber band stretched across an array. You extend the right end until the band covers enough elements to meet your target sum.

Once you've met the target, you try pulling in the left end to make the band shorter while still meeting the target. When it becomes too short (sum drops below target), you extend the right end again.

The key insight: because all numbers are positive, you never need to move a pointer backwards - each pointer only moves forward through the array once.

The optimal approach uses a sliding window with two pointers. Start with both pointers at the beginning. Expand the window by moving the right pointer and adding elements to the sum. Once the sum meets or exceeds the target, try shrinking the window from the left while maintaining a valid sum, tracking the minimum length. Because all numbers are positive, each pointer only moves forward once through the array, achieving linear time complexity.

def min_subarray_len(target, nums):
    """
    Find minimum length of contiguous subarray with sum >= target.
    Uses sliding window with two pointers for O(n) time complexity.
    """
    # Initialize variables
    n = len(nums)
    min_length = float('inf')
    window_sum = 0
    left = 0
    
    # Expand window with right pointer
    for right in range(n):
        # Add current element to window sum
        window_sum += nums[right]
        
        # Shrink window while sum is valid
        while window_sum >= target:
            # Update minimum length
            min_length = min(min_length, right - left + 1)
            
            # Remove leftmost element and shrink window
            window_sum -= nums[left]
            left += 1
    
    # Return result (0 if no valid subarray found)
    return min_length if min_length != float('inf') else 0

• sliding-window mastery: Understanding when and why to use sliding-window data structure for this type of problem pattern
• Algorithm optimization: Recognizing how to achieve O(n) time complexity through efficient problem decomposition
• Implementation patterns: Learning the key coding techniques that make this solution robust and maintainable
• Problem-solving approach: Developing intuition for when to apply this algorithmic pattern to similar challenges
• Performance analysis: Understanding the time and space complexity trade-offs and why they matter in practice