Minimum Size Subarray Sum [Sliding Window]

209.Minimum Size Subarray Sum

Array

Sliding Window

Two Pointers

Problem Statement:

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

Example:

Input:

target = 7
nums = [2,3,1,2,4,3]

→

Output:

2

The subarray [4,3] has the minimal length under the problem constraint.

Algorithm:

1. Use two pointers for sliding window
2. Expand window until sum >= target
3. Contract window while sum still valid
4. Track minimum window size seen

Complexity:

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

Java Solution:

public int minSubArrayLen(int target, int[] nums) {
    int i = 0, j = 0, sum = 0;
    int min = Integer.MAX_VALUE;
    
    while (j < nums.length) {
        // Expand window
        sum += nums[j];
        
        // Contract window while valid
        while (sum >= target) {
            min = Math.min(min, j - i + 1);
            sum -= nums[i];
            i++;
        }
        
        j++;
    }
    
    // Return 0 if no valid subarray found
    return min == Integer.MAX_VALUE ? 0 : min;
}

Python Solution:

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    i = curr_sum = 0
    min_len = float('inf')
    
    for j in range(len(nums)):
        # Expand window
        curr_sum += nums[j]
        
        # Contract window while valid
        while curr_sum >= target:
            min_len = min(min_len, j - i + 1)
            curr_sum -= nums[i]
            i += 1
    
    # Return 0 if no valid subarray found
    return min_len if min_len != float('inf') else 0

C++ Solution:

int minSubArrayLen(int target, vector<int>& nums) {
    int i = 0, j = 0, sum = 0;
    int min_len = INT_MAX;
    
    while (j < nums.size()) {
        // Expand window
        sum += nums[j];
        
        // Contract window while valid
        while (sum >= target) {
            min_len = min(min_len, j - i + 1);
            sum -= nums[i];
            i++;
        }
        
        j++;
    }
    
    // Return 0 if no valid subarray found
    return min_len == INT_MAX ? 0 : min_len;
}