Minimum Size Subarray Sum (LC 209)

Pattern: Sliding Window (variable size)
Difficulty: Medium
Key Concept: Expand the window until the sum is large enough, then shrink from the left to minimize length while the sum stays valid.

Problem Statement

You are given an array nums of positive integers and a positive integer target.

Return the minimum length of a contiguous subarray whose sum is greater than or equal to target. If no such subarray exists, return 0.

Input

• nums: int[] — all elements are positive
• target: int — positive

Output

• int — minimum length of a subarray with sum ≥ target, or 0 if impossible

Constraints (typical)

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

---

1. Algorithm & Pseudocode

Brute force (check every subarray)

minLen = infinity
for start from 0 to n-1:
    sum = 0
    for end from start to n-1:
        sum += nums[end]
        if sum >= target:
            minLen = min(minLen, end - start + 1)
            break   // extending end only increases length for this start
return minLen if minLen != infinity else 0

Optimal (variable-size sliding window)

Because all numbers are positive, when you extend right the sum only grows, and when you move left forward the sum only shrinks. That monotonicity lets you use one pass.

left = 0
sum = 0
minLen = infinity

for right from 0 to n-1:
    sum += nums[right]
    while sum >= target:
        minLen = min(minLen, right - left + 1)
        sum -= nums[left]
        left += 1

return minLen if minLen != infinity else 0

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why brute force is slow
   Every pair (start, end) is a candidate. There are on the order of n^2 subarrays, and summing each naively repeats work.

2. Why positivity matters
   If you could have negative numbers, shrinking the window might increase the sum, so a simple “expand then shrink” window does not capture all optimal subarrays. Here, positivity guarantees that once sum >= target, moving left right only decreases sum—so you can safely search for the shortest window ending at right.

3. What left represents
   left is the start of the current window. right is the end. The window is always nums[left..right].

4. Why the inner while sum >= target
   As long as the window still satisfies sum >= target, you can try to shorten it by moving left one step right. Each time you do, you might get a smaller length right - left + 1. Stop when sum < target (window too small) or left passes right.

5. Why we do not reset left to 0
   After we shrink, the next right might still allow a valid window that starts at the current left. Starting over from 0 would redo work and break the linear-time idea.

6. Integer.MAX_VALUE for “no answer yet”
   We need a sentinel larger than any real answer so Math.min works. If we finish and minLen is still that sentinel, return 0.

---

3. The Dry Run

Sample: target = 7, nums = [2, 3, 1, 2, 4, 3]
Optimal sliding window (indices 0-based).

Step	right	nums[right]	sum (after add)	sum >= 7?	Action in while	left after	minLen
init	—	—	0	no	—	0	∞
1	0	2	2	no	—	0	∞
2	1	3	5	no	—	0	∞
3	2	1	6	no	—	0	∞
4	3	2	8	yes	shrink: sum-=2 → 6	1	4
4b	—	—	6	no	exit while	1	4
5	4	4	10	yes	shrink: sum-=3 → 7	2	4
5b	—	—	7	yes	shrink: sum-=1 → 6	3	3
5c	—	—	6	no	exit while	3	3
6	5	3	9	yes	shrink: sum-=2 → 7	4	3
6b	—	—	7	yes	shrink: sum-=4 → 3	5	2
6c	—	—	3	no	exit while	5	2

Result: minLen = 2 (subarray [4, 3] at indices 4–5, sum 7).

---

4. Java Solution

Brute Force

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLen = Integer.MAX_VALUE;

        for (int start = 0; start < n; start++) {
            int sum = 0;
            for (int end = start; end < n; end++) {
                sum += nums[end];
                if (sum >= target) {
                    minLen = Math.min(minLen, end - start + 1);
                    break;
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

Time: O(n²) in the worst case (nested loops).
Space: O(1).

Optimal

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int 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];
                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

Time: O(n) — each index moves at most a constant number of times as left and right march forward.
Space: O(1).

---

5. The “Java vs. Others” Edge

• Integer.MAX_VALUE: Java uses this as a practical “infinity” for minimum-length problems. In C++ you often use INT_MAX from <climits>. In Python, float('inf') is common (or a very large int).
• Math.min: Works with int; no risk of forgetting a namespace (C++ std::min needs headers and care with macros).
• No unsigned index types: Loop indices are int; for huge arrays in competitive settings, be aware of overflow only if you multiply lengths—here lengths stay in int range per problem constraints.
• Contrast with Python: Python’s arbitrary-precision ints avoid overflow on sum, but Java int is fine for given LeetCode constraints; use long for sum if constraints allowed huge partial sums.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n²)	O(1)	Tries each start; inner loop can break early after first valid end.
Optimal	O(n)	O(1)	Relies on all nums[i] > 0; two pointers, each moves forward only.