LeetCode Solutions Blog

Minimum Size Subarray Sum

Number: 209

Difficulty: Medium

Paid? No

Problem Description

Given an array of positive integers nums and a positive integer target, find the minimal length of a contiguous subarray whose sum is greater than or equal to target. If no such subarray exists, return 0.

Key Insights

All numbers are positive, which allows for a sliding window approach.
A sliding window maintains a dynamic range [left, right] that expands or contracts to find candidate subarrays.
The window is expanded until the sum meets/exceeds the target, then contracted to seek the minimal candidate.
An O(n) solution is achievable with the sliding window technique; an alternative O(n log n) solution exists using prefix sums and binary search.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We use the sliding window approach:

Initialize two pointers, left and right, and a variable to maintain the current window sum.
As you iterate with the right pointer, add the current element to the window sum.
While the window sum is greater than or equal to target, try to reduce the window size by moving the left pointer forward and update the minimal length found.
If no valid window is found throughout the loop, return 0. This method works efficiently because adding an element increases the sum and removing it decreases the sum, so we maintain validity within a single pass.

Code Solutions

# Python implementation with detailed comments

def minSubArrayLen(target, nums):
    # Initialize the window pointers and variables
    n = len(nums)
    left = 0             # Left pointer of the sliding window
    window_sum = 0       # Sum of the current window
    min_len = float('inf')  # Track minimum length, start with infinity
    
    # Iterate over the array with right pointer
    for right in range(n):
        window_sum += nums[right]  # Expand the window by adding the current element
        
        # Contract the window as long as the current sum is large enough
        while window_sum >= target:
            # Update the minimum length found so far
            current_window_length = right - left + 1
            min_len = min(min_len, current_window_length)
            
            # Shrink the window from the left and subtract the value
            window_sum -= nums[left]
            left += 1
            
    # If the min_len wasn't updated, no valid subarray was found. Return 0.
    return 0 if min_len == float('inf') else min_len

# Example usage:
print(minSubArrayLen(7, [2,3,1,2,4,3]))  # Expected output: 2