[/dsa/leetcode]

209 - Minimum Size Subarray Sum

Thursday, 17 September 2026

<medium> [problem]

Sliding window that grows until the sum reaches the target, then shrinks from the left while it still does.

{array}{prefix sum}{sliding window}

Problem

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.

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length

Input: target = 4, nums = [1,4,4]
Output: 1

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4

Approach

Like 3, the window has no set size, but this time we want the shortest one. Move r forward and add each number to sum. As soon as sum reaches target, the window is good, so note its length, then take numbers off the left end and keep noting the length for as long as sum stays at or above target. Once it drops below, go back to moving r. This works because all numbers are positive: adding a number only makes the sum bigger and removing one only makes it smaller, so we never need to move l back.

target = 7, nums = [2,3,1,2,4,3]
r=0 [2]          sum=2
r=1 [2,3]        sum=5
r=2 [2,3,1]      sum=6
r=3 [2,3,1,2]    sum=8  len=4, remove 2 -> [3,1,2] sum=6
r=4 [3,1,2,4]    sum=10 len=4, remove 3 -> [1,2,4] sum=7
                        len=3, remove 1 -> [2,4]   sum=6
r=5 [2,4,3]      sum=9  len=3, remove 2 -> [4,3]   sum=7
                        len=2, remove 4 -> [3]     sum=3
answer = 2
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;
        int maxi = INT_MAX;
        for(int r = 0, l = 0; r < nums.size(); r++) {
            sum += nums[r];
            while(sum >= target) {
                maxi = min(maxi, r - l + 1);
                sum -= nums[l++];
            }
        }
        return maxi == INT_MAX ? 0 : maxi;
    }
};

sum fits in an int since it’s at most 10^5 * 10^4 = 10^9.

  • time: O(n) - each number is added once and removed at most once
  • space: O(1)
quantinium © 2026