Minimum Size Subarray Sum

Mediumsliding-windowarrayprefix-sum
Category: Sliding Window
Companies that ask this question:
AmazonFacebookGoogle
LeetCode →NeetCode →

Approach

Minimum Size Subarray Sum

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.

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

Intuition

Use a variable-size sliding window:

  • Expand right to increase sum
  • Contract left while sum >= target (to minimize length)
  • Track minimum length during valid windows

Since all numbers are positive, removing from left always decreases sum.

Pattern Recognition

This is a Variable-Size Sliding Window problem with:

  • Expand window to meet constraint
  • Contract window to optimize result
  • Monotonic property (positive numbers)

Approach

  1. Initialize: left = 0, currentSum = 0, minLen = infinity
  2. Expand Window (move right):
    • Add nums[right] to currentSum
    • While currentSum >= target:
      • Update minLen = min(minLen, right - left + 1)
      • Remove nums[left] from currentSum
      • Move left++
  3. Return: minLen if found, else 0

Edge Cases

  • No valid subarray (sum of all < target)
  • Single element >= target (return 1)
  • Entire array needed (return length)
  • Multiple subarrays with same minimum length

Complexity Analysis

  • Time Complexity: O(n) where n is length of nums
    • Each element visited at most twice (once by right, once by left)
    • Linear scan with two pointers
  • Space Complexity: O(1)
    • Only using a few variables

Solution

java
1class Solution {
2    public int minSubArrayLen(int target, int[] nums) {
3        int left = 0;
4        int currentSum = 0;
5        int minLen = Integer.MAX_VALUE;
6
7        for (int right = 0; right < nums.length; right++) {
8            // Expand window: add element
9            currentSum += nums[right];
10
11            // Contract window while sum >= target
12            while (currentSum >= target) {
13                minLen = Math.min(minLen, right - left + 1);
14                currentSum -= nums[left];
15                left++;
16            }
17        }
18
19        return minLen == Integer.MAX_VALUE ? 0 : minLen;
20    }
21}
22
Loading visualizer...