209. Minimum Size Subarray Sum

Medium

Problem Description

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.

Examples

Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

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
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def minSubArrayLen(target: int, nums: List[int]) -> int:
    if not nums:
        return 0
    
    min_length = float('inf')
    current_sum = 0
    left = 0
    
    for right in range(len(nums)):
        current_sum += nums[right]
        
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            currentSum -= nums[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0

Binary Search Solution:


def minSubArrayLen(target: int, nums: List[int]) -> int:
    if not nums:
        return 0
    
    # Calculate prefix sums
    prefix_sums = [0]
    for num in nums:
        prefix_sums.append(prefix_sums[-1] + num)
    
    min_length = float('inf')
    
    # For each starting point
    for i in range(len(nums)):
        # Binary search for end point
        left, right = i + 1, len(nums)
        while left <= right:
            mid = (left + right) // 2
            current_sum = prefix_sums[mid] - prefix_sums[i]
            if current_sum >= target:
                min_length = min(min_length, mid - i)
                right = mid - 1
            else:
                left = mid + 1
    
    return min_length if min_length != float('inf') else 0

Java Solution


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

C++ Solution


class Solution {
public:
    int minSubArrayLen(int target, vector& nums) {
        if (nums.empty()) {
            return 0;
        }
        
        int minLength = INT_MAX;
        int currentSum = 0;
        int left = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            currentSum += nums[right];
            
            while (currentSum >= target) {
                minLength = min(minLength, right - left + 1);
                currentSum -= nums[left];
                left++;
            }
        }
        
        return minLength == INT_MAX ? 0 : minLength;
    }
};

JavaScript Solution


/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    if (!nums.length) {
        return 0;
    }
    
    let minLength = Infinity;
    let currentSum = 0;
    let left = 0;
    
    for (let right = 0; right < nums.length; right++) {
        currentSum += nums[right];
        
        while (currentSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            currentSum -= nums[left];
            left++;
        }
    }
    
    return minLength === Infinity ? 0 : minLength;
};

C# Solution


public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }
        
        int minLength = int.MaxValue;
        int currentSum = 0;
        int left = 0;
        
        for (int right = 0; right < nums.Length; right++) {
            currentSum += nums[right];
            
            while (currentSum >= target) {
                minLength = Math.Min(minLength, right - left + 1);
                currentSum -= nums[left];
                left++;
            }
        }
        
        return minLength == int.MaxValue ? 0 : minLength;
    }
}

Complexity Analysis

Solution Explanation

There are two main approaches to solve this problem:

Key Points

Common Pitfalls

Edge Cases