Minimum Size Subarray Sum

Difficulty: Medium
Topics: Array, Binary Search, Sliding Window, Prefix Sum
Link: https://leetcode.com/problems/minimum-size-subarray-sum/

Problem Description

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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

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)).

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement
Given a sequence $nums$ of $n$ positive integers and threshold $target$ , identify the minimal window length $L_{min}$ such that there exists at least one contiguous subarray $nums[i:j]$ where $\sum_{k=i}^{j-1} nums[k] \geq target$ . Formally:

L_{min} = \min\{j-i \mid 0 \leq i \leq j \leq n, \sum_{k=i}^{j-1} nums[k] \geq target\}

Return 0 if no such subarray exists.

Beginner-Friendly Explanation
We’re looking for the shortest stretch of consecutive numbers in a list where their total sum reaches or exceeds a given target number. If no such stretch exists, we return zero.

Mathematical Formulation
Let $S(i,j) = \sum_{k=i}^{j-1} nums[k]$ be the subarray sum from index $i$ to $j-1$ . The problem reduces to:

\min_{0 \leq i \leq j \leq n} (j-i) \quad \text{subject to} \quad S(i,j) \geq target

with convention $\min(\emptyset) = 0$ .

Constraint Analysis

$1 \leq target \leq 10^9$ : Large target values imply single-element solutions may not suffice, requiring multi-element sums
$1 \leq nums.length \leq 10^5$ : Quadratic solutions ( $O(n^2)$ ) are infeasible (up to $10^{10}$ operations)
$1 \leq nums[i] \leq 10^4$ : All elements positive guarantees prefix sums are strictly increasing, enabling binary search
Edge Cases:
- Single element satisfies target (Example 2)
- Entire array sum < target (Example 3)
- First/last elements critical to solution
- Multiple valid subarrays of same minimal length

2. Intuition Scaffolding

Real-World Metaphor
Imagine you’re saving money in daily increments. You need to find the shortest consecutive period where your total savings reach a goal amount. Each day you save a different positive amount, and you want the fewest number of days possible.

Gaming Analogy
In a role-playing game, you need to collect enough experience points from consecutive monsters to level up. Each monster gives a fixed XP amount. You want to defeat the fewest monsters in a row to reach the level-up threshold.

Math Analogy
Given a strictly increasing sequence (prefix sums), find the minimal distance between two points where the difference exceeds a threshold. This transforms the problem into searching for pairs in a sorted array.

Common Pitfalls

Global Min/Max Fallacy: Assuming the smallest/largest elements alone determine the solution
Over-Eager Shrinking: Reducing window size too quickly before verifying constraints
Binary Search Misapplication: Applying binary search without monotonic property verification
Off-by-One Errors: Incorrect index handling in sliding window boundaries
Early Termination: Stopping at first valid solution without checking for shorter alternatives
Negative Number Assumption: Assuming elements can be negative (constraints guarantee positivity)

3. Approach Encyclopedia

Brute Force ( $O(n^3)$ → $O(n^2)$ )

# Naive O(n^3) - check all subarrays
def minSubArrayLen(target, nums):
    n = len(nums)
    min_len = float('inf')
    for i in range(n):
        for j in range(i, n):
            current_sum = 0
            for k in range(i, j+1):  # O(n) sum calculation
                current_sum += nums[k]
            if current_sum >= target:
                min_len = min(min_len, j-i+1)
    return min_len if min_len != float('inf') else 0

Optimized Brute Force ( $O(n^2)$ )

# Precompute prefix sums O(n^2)
def minSubArrayLen(target, nums):
    n = len(nums)
    min_len = float('inf')
    
    # Prefix sum array
    prefix = [0] * (n+1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    
    for i in range(n):
        for j in range(i, n):
            current_sum = prefix[j+1] - prefix[i]
            if current_sum >= target:
                min_len = min(min_len, j-i+1)
                break  # Early break for current i
    return min_len if min_len != float('inf') else 0

Binary Search Approach ( $O(n \log n)$ )

def minSubArrayLen(target, nums):
    n = len(nums)
    min_len = float('inf')
    
    # Prefix sums (strictly increasing due to positive numbers)
    prefix = [0] * (n+1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    
    for i in range(n):
        # Binary search for minimal j where prefix[j] - prefix[i] >= target
        left, right = i, n
        while left < right:
            mid = (left + right) // 2
            if prefix[mid+1] - prefix[i] >= target:
                right = mid
            else:
                left = mid + 1
        
        if left < n and prefix[left+1] - prefix[i] >= target:
            min_len = min(min_len, left - i + 1)
    
    return min_len if min_len != float('inf') else 0

Sliding Window ( $O(n)$ )

def minSubArrayLen(target, nums):
    n = len(nums)
    min_len = float('inf')
    left = 0
    current_sum = 0
    
    for right in range(n):
        current_sum += nums[right]
        
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0

Complexity Proofs

Brute Force: Triple nested loops → $\sum_{i=0}^{n-1} \sum_{j=i}^{n-1} (j-i+1) = O(n^3)$
Prefix + Brute: $\sum_{i=0}^{n-1} (n-i) = \frac{n(n+1)}{2} = O(n^2)$
Binary Search: $n$ iterations × $O(\log n)$ search = $O(n \log n)$
Sliding Window: Each element processed at most twice → $O(2n) = O(n)$

Visualization

Sliding Window Operation:
nums = [2,3,1,2,4,3], target = 7

Step 0: [2]        sum=2  | min_len=∞
Step 1: [2,3]      sum=5  | min_len=∞  
Step 2: [2,3,1]    sum=6  | min_len=∞
Step 3: [2,3,1,2]  sum=8  | VALID → min_len=4
        Shrink: [3,1,2] sum=6 | min_len=4
Step 4: [3,1,2,4]  sum=10 | VALID → min_len=4
        Shrink: [1,2,4] sum=7 | VALID → min_len=3
        Shrink: [2,4]   sum=6 | min_len=3
Step 5: [2,4,3]    sum=9  | VALID → min_len=3
        Shrink: [4,3]   sum=7 | VALID → min_len=2 ← ANSWER

4. Code Deep Dive

Optimal Sliding Window Solution

def minSubArrayLen(target, nums):
    n = len(nums)
    min_len = float('inf')  # Initialize with infinity for comparison
    left = 0  # Left boundary of sliding window
    current_sum = 0  # Running sum of current window
    
    for right in range(n):  # Expand window to the right
        current_sum += nums[right]  # Add new element to window
        
        # Shrink window from left while condition satisfied
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)  # Update minimal length
            current_sum -= nums[left]  # Remove leftmost element
            left += 1  # Move left boundary
    
    return min_len if min_len != float('inf') else 0  # Handle no solution case

Line-by-Line Analysis

Line 2: Get array length once for efficiency
Line 3: Initialize with infinity to easily track minimum
Line 4: Left pointer starts at beginning of array
Line 5: Running sum initialized to zero
Line 7: Right pointer traverses entire array
Line 8: Expand window by including next element
Line 11: Critical while loop - shrink when sum sufficient
Line 12: Calculate current window length and update minimum
Line 13: Remove left element from sum before moving pointer
Line 14: Contract window from left side
Line 17: Return 0 if no valid subarray found

Edge Case Handling

Example 1 (target=7, nums=[2,3,1,2,4,3]): Window shrinks correctly to find [4,3]
Example 2 (target=4, nums=[1,4,4]): Single element [4] satisfies immediately
Example 3 (target=11, nums=[1,1,1,1,1,1,1,1]): Total sum 8 < 11 → returns 0
Single Element: Handled by right pointer capturing single-element windows
Empty Input: Constraint guarantees nums.length ≥ 1

5. Complexity War Room

Hardware-Aware Analysis

Memory: Sliding window uses $O(1)$ extra space (3 variables) ~ 24 bytes
Cache Performance: Sequential array access maximizes cache line utilization
CPU Pipeline: Predictable loop structure enables branch prediction optimization
At Scale: For $n=10^5$ , approximately $2\times10^5$ operations → ~0.2ms on modern CPUs

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	$O(n^3)$	$O(1)$	10/10	❌ Fails constraints
Prefix + Brute	$O(n^2)$	$O(n)$	9/10	❌ Fails large N
Binary Search	$O(n \log n)$	$O(n)$	7/10	✅ Good alternative
Sliding Window	$O(n)$	$O(1)$	8/10	✅ Optimal choice

6. Pro Mode Extras

Algorithm Variants

Fixed Window Size: Find subarrays of exactly length $k$ with sum ≥ target
Circular Array: Subarray can wrap around end to beginning
At Most K Elements: Find minimal length where sum ≤ target with max k elements
Negative Numbers Allowed: Requires different approach (hash map + prefix sums)

Interview Cheat Sheet

First Mention: Always state time/space complexity upfront
Positive Numbers: Emphasize this enables sliding window approach
Two Pointer Template: Expand right until condition met, then shrink left
Testing Strategy:
- Single element cases
- Entire array as solution
- No solution case
- Multiple valid solutions

Follow-up Solutions

# O(n log n) Binary Search variant
def minSubArrayLen(target, nums):
    n = len(nums)
    ans = float('inf')
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)
    
    for i in range(n):
        to_find = target + prefix[i]
        bound = bisect.bisect_left(prefix, to_find)
        if bound != len(prefix):
            ans = min(ans, bound - i)
    
    return ans if ans != float('inf') else 0

#209 - Minimum Size Subarray Sum