Course4all
Join us on telegram
Home/dsa/Sliding Window/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 contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Visual Representation

target = 7, nums = [2, 3, 1, 2, 4, 3] [2, 3, 1, 2], 4, 3 (Sum: 8 >= 7, Len: 4) 2, [3, 1, 2, 4], 3 (Sum: 10 >= 7, Len: 4) 2, 3, 1, [2, 4, 3] (Sum: 9 >= 7, Len: 3) -> MINIMAL
Medium

Examples

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

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

Approach 1

Level I: Brute Force (O(N^2))

Intuition

Check all possible subarrays and find the one with sum >= target and minimum length.

Thought Process

  1. Use two nested loops to define every subarray nums[i...j].
  2. Calculate the sum of each subarray.
  3. If sum >= target, update minLen = min(minLen, j - i + 1).

Pattern: Subarray Enumeration

⏱ O(N^2)💾 O(1)
java
public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length, minLen = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= target) {
                    minLen = Math.min(minLen, j - i + 1);
                    break;
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}
Approach 2

Level III: Optimal (Variable Sliding Window)

Intuition

Categorization

This is the classic Variable Size Window problem. We expand the window until the sum meets the target, then shrink from the left to find the smallest valid window.

Thought Process

  1. Maintain a windowSum and a left pointer.
  2. Iterate right from 0 to n-1 (Expand).
  3. Add nums[right] to windowSum.
  4. While windowSum >= target:
    • Update minLen with right - left + 1.
    • Subtract nums[left] from windowSum and increment left (Shrink).

Mandatory Variables

  • left: Pointer to the start of the window.
  • windowSum: Current sum of the window content.
  • minLen: Smallest valid window length found.
⏱ O(N) - Each element is visited at most twice.💾 O(1)

Detailed Dry Run

StepLRwindowSumminLenAction
1002infExpand
2015infExpand
3026infExpand
40384Sum >= 7! Update minLen, Shrink L
51364Sum < 7. Expand R
java
public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, sum = 0, minLen = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}
← Previous QuestionMaximum Sum Subarray of Size K
Next Question →Longest Substring Without Repeating Characters