Minimum Size Subarray Sum

Share

Find minimum length subarray with sum >= target.

Example 1
Input: target=7, nums=[2,3,1,2,4,3] → Output: 2. Subarray [4,3] has sum >= 7.
Example 2
Input: target=4, nums=[1,4,4] → Output: 1

Solution Approach

Sliding window: expand right, shrink left when sum >= target.

  • Sliding window with left and right pointers
  • Expand right, add to sum
  • When sum >= target: update min length, subtract left element, advance left
  • Return min or 0 if not found
Java
public int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, min = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            min = Math.min(min, right - left + 1);
            sum -= nums[left++];
        }
    }
    return min == Integer.MAX_VALUE ? 0 : min;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)