Minimum Size Subarray Sum [Code + Visualization]

Sliding Window Medium

Python Java C++

def minSubArrayLen(target: int, nums: List[int]) -> int:
    # Initialize window pointers and values
    i = j = 0
    currSum = 0
    minLen = float('inf')
    
    # Expand window with j pointer
    while j < len(nums):
        currSum += nums[j]
        
        # Shrink window while sum is sufficient
        while currSum >= target:
            minLen = min(minLen, j - i + 1)
            currSum -= nums[i]
            i += 1
            
        j += 1
        
    return 0 if minLen == float('inf') else minLen

class Solution {
    // Easy sliding window but algo can get tricky make sure edge cases are handled
    public int minSubArrayLen(int s, int[] nums) {
        int i = 0;
        int j = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        
        while (j < nums.length) {
            sum += nums[j];
                        
            while (sum >= s) {
                min = Math.min(min, j - i + 1);
                sum -= nums[i];
                i++;
            }
            
            j++;
        }
        
        return min == Integer.MAX_VALUE ? 0 : min;     
    }
}

class Solution {
public:
    int minSubArrayLen(int target, vector& nums) {
        // Initialize window pointers and values
        int i = 0, j = 0;
        int currSum = 0;
        int minLen = INT_MAX;
        
        // Expand window with j pointer
        while (j < nums.size()) {
            currSum += nums[j];
            
            // Shrink window while sum is sufficient
            while (currSum >= target) {
                minLen = min(minLen, j - i + 1);
                currSum -= nums[i];
                i++;
            }
            
            j++;
        }
        
        return minLen == INT_MAX ? 0 : minLen;
    }
};

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.

Detailed Explanation

Approach

This solution uses a sliding window approach with two pointers. The right pointer (j) expands the window to increase the sum, while the left pointer (i) shrinks the window when the sum becomes sufficient. This allows us to find the minimum window size that satisfies our condition.

Key Concepts

1. Two Pointers: Left (i) and right (j) define window boundaries
2. Running Sum: Track sum of current window
3. Window Shrinking: Try to minimize window size when sum is sufficient
4. Minimum Tracking: Update minimum length when valid window found

Algorithm Steps

1. Initialize variables:
   • Two pointers i and j at start
   • Running sum starts at 0
   • Minimum length starts at infinity
2. While j < array length:
   • Add nums[j] to sum (expand window)
   • While sum ≥ target:
     • Update minimum length if current window smaller
     • Subtract nums[i] from sum
     • Increment i (shrink window)
   • Increment j
3. Return 0 if no valid window found, else return minimum length

Time and Space Complexity

• Time Complexity: O(n) - Each element processed at most twice (once by each pointer)
• Space Complexity: O(1) - Only using constant extra space

Previous Step Next Step Reset

Target Sum

7

Current Sum

0

Window Size

0

Minimum Length

∞

Expanding Window

Click "Next Step" to begin the visualization

Why This Works

The sliding window approach works because:

• All elements are positive, so sum increases with window size
• If a window sum is sufficient, no larger window starting at same position needed
• If a window sum is insufficient, no smaller window ending at same position possible
• We never need to move backwards, making one pass sufficient

Edge Cases

• Empty array: Return 0
• No valid subarray: Return 0
• Single element ≥ target: Return 1
• All elements required: Return array length

Common Mistakes

• Not handling case when no valid subarray exists
• Incorrect window size calculation (off-by-one)
• Not shrinking window as much as possible
• Forgetting to update minimum length