Course4all
Join us on telegram
Home/dsa/Two Pointers/Minimum Size Subarray Sum

Minimum Size Subarray Sum

Master this topic with zero to advance depth.

Minimum Size Subarray Sum

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.

Nums: [2, 3, 1, 2, 4, 3], Target: 7 Step 1: Expand [2, 3, 1, 2], Sum = 8 (>=7). Len = 4. Step 2: Shrink [3, 1, 2], Sum = 6 (<7). Expand. Step 3: Expand [3, 1, 2, 4], Sum = 10 (>=7). Len = 4. Step 4: Shrink [1, 2, 4], Sum = 7 (>=7). Len = 3. Step 5: Shrink [2, 4], Sum = 6 (<7). Expand. Step 6: Expand [2, 4, 3], Sum = 9 (>=7). Len = 3. Step 7: Shrink [4, 3], Sum = 7 (>=7). Len = 2. (MIN)
Medium

Examples

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2

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

Approach 1

Level I: Brute Force (Check All Subarrays)

Intuition

Iterate through every possible subarray, calculate its sum, and check if it's >= target. Keep track of the minimum length found.

⏱ O(N^2)💾 O(1)

Detailed Dry Run

Input: target=7, nums=[2,3,1]

  • Subarrays: [2], [2,3], [2,3,1], [3], [3,1], [1].
  • All sums < 7. No valid subarray found.
java
public int minSubArrayLen(int target, int[] nums) {
    int minLen = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum >= target) {
                minLen = Math.min(minLen, j - i + 1);
                break;
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

⚠️ Common Pitfalls & Tips

O(N^2) will time out for arrays of size 10^5.

Approach 2

Level II: Better (Prefix Sums + Binary Search)

Intuition

Since all numbers are positive, the prefix sums array will be strictly increasing. For each index i, we can use binary search to find the smallest index j such that sum(0..j) - sum(0..i-1) >= target.

⏱ O(N log N)💾 O(N) (for prefix sums array)

Detailed Dry Run

target=7, nums=[2,3,1,2,4,3] PrefixSums: [0, 2, 5, 6, 8, 12, 15]

  • For i=0 (val 2): binary search for 7+0=7 in PrefixSums → Found 8 at index 4. Len = 4.
  • For i=4 (val 4): binary search for 7+8=15 → Found 15 at index 6. Len = 2.
java
public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length, minLen = Integer.MAX_VALUE;
    int[] sums = new int[n + 1];
    for (int i = 1; i <= n; i++) sums[i] = sums[i - 1] + nums[i - 1];
    for (int i = 1; i <= n; i++) {
        int toFind = target + sums[i - 1];
        int bound = Arrays.binarySearch(sums, toFind);
        if (bound < 0) bound = -bound - 1;
        if (bound <= n) minLen = Math.min(minLen, bound - (i - 1));
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

⚠️ Common Pitfalls & Tips

Requires binary search logic (or built-in functions) and O(N) extra space.

Approach 3

Level III: Optimal (Sliding Window)

Intuition

Since all numbers are positive, a larger window will always have a larger sum. We can use a sliding window defined by two pointers, left and right. We expand right to increase the sum and shrink left to minimize the window size while maintaining the condition sum >= target.

⏱ O(N) (Each element is visited at most twice)💾 O(1)

Detailed Dry Run

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

  1. r=0..2: sum=6.
  2. r=3: sum=8. minLen=4, sum-=nums[0]=6, l=1.
  3. r=4: sum=10. minLen=4, sum-=nums[1]=7, minLen=3. sum-=nums[2]=6, l=3.
  4. r=5: sum=9. minLen=3, sum-=nums[3]=7, minLen=2. sum-=nums[4]=4, l=5. Result: 2
java
public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0, sum = 0, minLen = Integer.MAX_VALUE;
        for (int r = 0; r < nums.length; r++) {
            sum += nums[r];
            while (sum >= target) {
                minLen = Math.min(minLen, r - l + 1);
                sum -= nums[l++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

⚠️ Common Pitfalls & Tips

If all elements are positive, the window sum is monotonic. If negative numbers were present, this approach wouldn't work.

← Previous QuestionValid Palindrome II
Next Question →Reverse Words in a String