36. Minimum Size Subarray Sum

🔗 LeetCode Problem: 209. Minimum Size Subarray Sum
📊 Difficulty: Medium
🏷️ Topics: Array, Binary Search, Sliding Window, Prefix 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.

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

Constraints: - 1 <= target <= 10^9 - 1 <= nums.length <= 10^5 - 1 <= nums[i] <= 10^4

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

---

🎨 Visual Understanding

The Problem Visualized

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

All subarrays with sum >= 7:
[2, 3, 1, 2]    → sum = 8, length = 4
[2, 3, 1, 2, 4] → sum = 12, length = 5
[3, 1, 2, 4]    → sum = 10, length = 4
[2, 4, 3]       → sum = 9, length = 3
[4, 3]          → sum = 7, length = 2 ✓ (minimum)
[1, 2, 4, 3]    → sum = 10, length = 4

Answer: 2

Key Difference: Variable Window Size

Previous problem (Maximum Average Subarray):
- FIXED window size k
- Slide window, track maximum

This problem (Minimum Size Subarray Sum):
- VARIABLE window size
- Expand when sum < target
- Shrink when sum >= target
- Track minimum length

Visual:
[2, 3, 1, 2, 4, 3]
 L     R           → sum = 6 < 7, expand
 L        R        → sum = 8 >= 7, shrink & record
    L     R        → sum = 6 < 7, expand
    L        R     → sum = 10 >= 7, shrink & record
       L     R     → sum = 7 >= 7, shrink & record
          L  R     → sum = 6 < 7, expand
          L     R  → sum = 9 >= 7, shrink & record
             L  R  → sum = 7 >= 7, found [4,3] length 2!

Why Sliding Window Works

Key insight: 
If subarray [i...j] has sum >= target,
then [i...j+1], [i...j+2] also have sum >= target.

No need to keep expanding once we meet target!
Instead, try to minimize by shrinking from left.

Strategy:
1. Expand window (right++) until sum >= target
2. Shrink window (left++) while sum >= target
3. Track minimum length during shrinking
4. Repeat until right reaches end

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Check all subarrays:
1. For each starting position i
2. For each ending position j (from i to end)
3. Calculate sum of subarray [i...j]
4. If sum >= target, record length
5. Return minimum length

Why This Works: - Checks all possibilities - Guaranteed to find answer if exists - Easy to understand

Why This Fails Requirements: - Time complexity O(n²) or O(n³) - Recalculates sum for overlapping subarrays - Too slow for large arrays - Not optimal for interviews

Implementation

public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int 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;  // No need to expand further
            }
        }
    }

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

⏰ Time: O(n²) - for each start, expand until target reached
💾 Space: O(1) - only variables

---

✅ Approach 2: Sliding Window (Optimal)

The Breakthrough Insight 💡

Core Logic:

Use variable-size sliding window:

1. Expand window: Add right element, right++
2. While sum >= target:
   - Record current length
   - Shrink window: Remove left element, left++
3. Repeat until right reaches end

Key insight: Once sum >= target, try to minimize
by shrinking from left, not by expanding more

Visual Explanation:

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

Step 1: Expand until sum >= target
[2] → sum = 2 < 7
[2, 3] → sum = 5 < 7
[2, 3, 1] → sum = 6 < 7
[2, 3, 1, 2] → sum = 8 >= 7 ✓

Step 2: Shrink while sum >= target
[2, 3, 1, 2] → length = 4, record
[3, 1, 2] → sum = 6 < 7, stop shrinking

Step 3: Continue expanding
[3, 1, 2, 4] → sum = 10 >= 7 ✓

Step 4: Shrink while sum >= target
[3, 1, 2, 4] → length = 4
[1, 2, 4] → sum = 7 >= 7, length = 3, record
[2, 4] → sum = 6 < 7, stop

Continue until end...
Final minimum: 2 (subarray [4, 3])

Why This Works:

Two-pointer property for positive numbers:
- If sum < target: Need more elements → expand right
- If sum >= target: Try to minimize → shrink left

Time: O(n)
- Right pointer visits each element once
- Left pointer visits each element at most once
- Total: each element visited at most twice

Implementation

public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int left = 0;
    int sum = 0;
    int minLen = Integer.MAX_VALUE;

    for (int right = 0; right < n; right++) {
        // Expand window by adding right element
        sum += nums[right];

        // Shrink window while sum >= target
        while (sum >= target) {
            // Update minimum length
            minLen = Math.min(minLen, right - left + 1);

            // Remove left element and shrink
            sum -= nums[left];
            left++;
        }
    }

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

⏰ Time: O(n) - each element visited at most twice
💾 Space: O(1) - only variables

---

🎯 Approach 3: Prefix Sum + Binary Search

The Follow-up Solution 💡

Core Logic:

Use prefix sum array with binary search:

1. Build prefix sum array: prefix[i] = sum of nums[0...i-1]
2. For each starting position i:
   - Need subarray sum >= target
   - prefix[j] - prefix[i] >= target
   - prefix[j] >= target + prefix[i]
   - Binary search for smallest j
3. Track minimum length

Time: O(n log n)

Implementation

public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;

    // Build prefix sum array
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    int minLen = Integer.MAX_VALUE;

    // For each starting position
    for (int i = 0; i < n; i++) {
        // Binary search for ending position
        int toFind = target + prefix[i];
        int idx = binarySearch(prefix, toFind);

        if (idx != -1) {
            minLen = Math.min(minLen, idx - i);
        }
    }

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

private int binarySearch(int[] prefix, int target) {
    int left = 0;
    int right = prefix.length - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (prefix[mid] >= target) {
            result = mid;
            right = mid - 1;  // Look for smaller index
        } else {
            left = mid + 1;
        }
    }

    return result;
}

⏰ Time: O(n log n) - O(n) for prefix + O(n × log n) for binary searches
💾 Space: O(n) - prefix sum array

---

🔍 Step-by-Step Execution

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

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [2, 3, 1, 2, 4, 3]
target = 7
left = 0, sum = 0, minLen = ∞


Step 1: right = 0, nums[0] = 2
═══════════════════════════════════════════════════════════════════
Expand: sum = 0 + 2 = 2
Window: [2]

Check: sum (2) >= target (7)? NO
Don't shrink

left = 0, sum = 2, minLen = ∞


Step 2: right = 1, nums[1] = 3
═══════════════════════════════════════════════════════════════════
Expand: sum = 2 + 3 = 5
Window: [2, 3]

Check: sum (5) >= target (7)? NO
Don't shrink

left = 0, sum = 5, minLen = ∞


Step 3: right = 2, nums[2] = 1
═══════════════════════════════════════════════════════════════════
Expand: sum = 5 + 1 = 6
Window: [2, 3, 1]

Check: sum (6) >= target (7)? NO
Don't shrink

left = 0, sum = 6, minLen = ∞


Step 4: right = 3, nums[3] = 2
═══════════════════════════════════════════════════════════════════
Expand: sum = 6 + 2 = 8
Window: [2, 3, 1, 2]

Check: sum (8) >= target (7)? YES
Shrink:
  minLen = min(∞, 3-0+1) = 4
  sum = 8 - 2 = 6, left = 1
  Window: [3, 1, 2]

Check: sum (6) >= target (7)? NO
Stop shrinking

left = 1, sum = 6, minLen = 4


Step 5: right = 4, nums[4] = 4
═══════════════════════════════════════════════════════════════════
Expand: sum = 6 + 4 = 10
Window: [3, 1, 2, 4]

Check: sum (10) >= target (7)? YES
Shrink:
  minLen = min(4, 4-1+1) = 4
  sum = 10 - 3 = 7, left = 2
  Window: [1, 2, 4]

Check: sum (7) >= target (7)? YES
Shrink again:
  minLen = min(4, 4-2+1) = 3
  sum = 7 - 1 = 6, left = 3
  Window: [2, 4]

Check: sum (6) >= target (7)? NO
Stop shrinking

left = 3, sum = 6, minLen = 3


Step 6: right = 5, nums[5] = 3
═══════════════════════════════════════════════════════════════════
Expand: sum = 6 + 3 = 9
Window: [2, 4, 3]

Check: sum (9) >= target (7)? YES
Shrink:
  minLen = min(3, 5-3+1) = 3
  sum = 9 - 2 = 7, left = 4
  Window: [4, 3]

Check: sum (7) >= target (7)? YES
Shrink again:
  minLen = min(3, 5-4+1) = 2 ✓
  sum = 7 - 4 = 3, left = 5
  Window: [3]

Check: sum (3) >= target (7)? NO
Stop shrinking

left = 5, sum = 3, minLen = 2


Right pointer reached end
═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 2
═══════════════════════════════════════════════════════════════════

---

🔍 Edge Cases

Case 1: No valid subarray
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Explanation: Sum of all elements = 8 < 11

Case 2: Single element sufficient
Input: target = 4, nums = [1,4,4]
Output: 1
Explanation: nums[1] = 4 >= 4

Case 3: Entire array needed
Input: target = 15, nums = [1,2,3,4,5]
Output: 5
Explanation: 1+2+3+4+5 = 15

Case 4: All elements equal
Input: target = 10, nums = [5,5,5,5]
Output: 2
Explanation: [5,5] = 10

Case 5: Large numbers
Input: target = 100, nums = [99,1]
Output: 2
Explanation: 99+1 = 100

Case 6: Target equals single element
Input: target = 7, nums = [1,2,7,3]
Output: 1
Explanation: nums[2] = 7

Case 7: First element is answer
Input: target = 10, nums = [10,1,2,3]
Output: 1

Case 8: Last elements form answer
Input: target = 5, nums = [1,1,1,1,5]
Output: 1

---

Common Mistakes

Mistake 1: Not handling "no valid subarray" case
❌ Wrong: 
    return minLen;  // Could be Integer.MAX_VALUE
✓ Right: 
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
Reason: Need to return 0 if no valid subarray found

Mistake 2: Using if instead of while for shrinking
❌ Wrong: 
    if (sum >= target) {
        minLen = Math.min(minLen, right - left + 1);
        sum -= nums[left];
        left++;
    }
✓ Right: 
    while (sum >= target) {
        minLen = Math.min(minLen, right - left + 1);
        sum -= nums[left];
        left++;
    }
Reason: Need to shrink as much as possible while valid

Mistake 3: Updating minLen after shrinking
❌ Wrong: 
    while (sum >= target) {
        sum -= nums[left];
        left++;
    }
    minLen = Math.min(minLen, right - left + 1);
✓ Right: 
    while (sum >= target) {
        minLen = Math.min(minLen, right - left + 1);
        sum -= nums[left];
        left++;
    }
Reason: Update before shrinking to get correct length

Mistake 4: Wrong window size calculation
❌ Wrong: 
    minLen = Math.min(minLen, right - left);
✓ Right: 
    minLen = Math.min(minLen, right - left + 1);
Reason: Need +1 for inclusive range

Mistake 5: Breaking too early
❌ Wrong: 
    if (sum >= target) {
        minLen = Math.min(minLen, right - left + 1);
        break;  // Wrong!
    }
✓ Right: 
    while (sum >= target) {
        minLen = Math.min(minLen, right - left + 1);
        sum -= nums[left];
        left++;
    }
Reason: Need to continue to find potentially smaller windows

Mistake 6: Not handling negative numbers
❌ Wrong: 
    // Assuming all numbers are positive
✓ Right: 
    // This solution only works for positive numbers
    // For negative numbers, need different approach
Reason: Problem states all numbers are positive

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(1)
  Use: Only for understanding

Approach 2: Sliding Window (RECOMMENDED)
  Time: O(n)
  Space: O(1)
  Use: Optimal for positive numbers

Approach 3: Prefix Sum + Binary Search
  Time: O(n log n)
  Space: O(n)
  Use: Follow-up solution, alternative approach

🔑 The Core Insight

Variable-Size Sliding Window Pattern:

Key Characteristics:
- Window size VARIES (not fixed)
- Expand when condition not met
- Shrink when condition met
- Track optimum during shrinking

Decision Logic:
- sum < target → EXPAND (right++)
- sum >= target → SHRINK (left++) while tracking minimum

Why It Works for Positive Numbers:
- Adding elements increases sum
- Removing elements decreases sum
- Once sum >= target, try to minimize length
- Each element visited at most twice (O(n))

Template:
1. Initialize left = 0, sum = 0, result = ∞
2. For right from 0 to n-1:
   - Add nums[right] to sum
   - While sum >= target:
     * Update result
     * Remove nums[left], left++
3. Return result (or 0 if none found)

Key Difference from Fixed Window:
Fixed Window: Always size k, slide uniformly
Variable Window: Expand/shrink based on condition

🎯 Pattern Recognition

Problem Type: Minimum/Maximum Length Subarray with Constraint
Core Pattern: Variable-Size Sliding Window

When to Apply:
✓ Finding subarray with specific sum/property
✓ Looking for minimum/maximum length
✓ All elements are positive (for this technique)
✓ Can expand and shrink window based on condition
✓ Want O(n) time complexity

Key Techniques:
→ Two pointers (left, right) for window
→ Expand window: right++
→ Shrink window: left++ (while condition met)
→ Track optimum during shrinking
→ Running sum for efficient calculation

IMPORTANT: Works for positive numbers only!
For negative numbers, need different approach (DP or prefix sum)

Related Problems:
- Maximum Size Subarray Sum Equals k (LC 325)
- Longest Substring with At Most K Distinct Characters (LC 340)
- Subarrays with K Different Integers (LC 992)
- Minimum Window Substring (LC 76)

🧠 Interview Strategy

Step 1: "Need minimum length subarray with sum >= target"
Step 2: "All numbers positive - can use sliding window"
Step 3: "Variable window: expand when sum < target"
Step 4: "Shrink when sum >= target, track minimum"
Step 5: "O(n) time, each element visited at most twice"

Key Points to Mention:
- Variable-size sliding window (not fixed)
- Two pointers: left and right
- Expand until condition met
- Shrink while condition still met
- Track minimum during shrinking
- O(n) time, O(1) space
- Works because all numbers are positive
- Follow-up: O(n log n) with prefix sum + binary search

---

📝 Quick Revision Notes

🎯 Core Concept:

Variable-size sliding window for positive numbers. Expand when sum < target, shrink while sum >= target, track minimum length.

⚡ Quick Implementation:

  public int minSubArrayLen(int k, int[] a) {
    int res = Integer.MAX_VALUE;
    int left = 0;
    int right = 0;
    int runningSum = 0;
    int len = a.length;

    while (right < len) {
      runningSum += a[right];

      // if still window did not cover the sum, expand the window towards right.
      if (runningSum < k) {
        right++;
        // System.out.println("left: " + left + ", right: " + right + ", running sum: "
        // + runningSum + ", res: " + res);

        continue;
      }

      // update res (window size) to min value.
      res = Math.min(res, right - left + 1);

      // Now try to shrink window
      while (left <= right && runningSum >= k) {
        res = Math.min(res, right - left + 1); // update the result only when condition satisfies
        runningSum -= a[left]; // as we are shrinking
        left++;
      }

      right++;
    }

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

🔑 Key Insights:

• Variable window: Size changes based on sum
• Expand: sum += nums[right] when sum < target
• Shrink: sum -= nums[left]; left++ while sum >= target
• Track minimum: Update before shrinking (to get correct length)
• Use while: Not if, to shrink as much as possible
• Return: 0 if minLen still MAX_VALUE (no valid subarray)
• Window size: right - left + 1 (inclusive)
• Time: O(n) - each element visited at most twice
• Space: O(1) - only variables
• Key: Works for positive numbers only!

🎪 Memory Aid:

"EXPAND till valid, SHRINK while valid, track MIN!"
Think: "Variable window: grow till meet, shrink till can't"

---

Related Patterns

• Maximum Size Subarray Sum Equals k (LC 325)
• Longest Substring with At Most K Distinct Characters (LC 340)
• Minimum Window Substring (LC 76)
• Subarrays with K Different Integers (LC 992)

---

Happy practicing! 🎯