Minimum Size Subarray Sum Problem

Imagine you are running an e-commerce website. Your fraud detection system flags an alert if a user spends ($10,000) or more. To minimize false positives, you don't care about total lifetime spending — you want to catch the shortest consecutive sequence of transactions that triggers that flag. In computer science, this is known as the Minimum Size Subarray Sum problem. Today, we will break down the problem, ditch the slow nested loops, and master the Sliding Window technique to solve it in lightning-fast linear time.

🏃‍♂️ The Challenge

Given an array of positive integers nums and a positive integer target, find the minimal length of a contiguous subarray whose sum is greater than or equal to target. If there isn't one, return 0 instead.

Example:

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

Output: 2

Explanation: The subarray [4, 3] has the minimal length (2) under the problem constraint since $4 + 3 >= 7$

🚫 The Naive Way: Brute Force $O(n^2)$

The intuitive approach is to check every single possible subarray. You start at index $0$, add numbers until you hit the target, record the length, and then reset and do the same starting at index $1$.

Why it fails: This requires two nested loops. If your array has $100,000$ items, your code will perform billions of operations. It will be timing out on any production system or coding interview platform.

💡 The Smarter Way: The Sliding Window $O(n)$

Instead of resetting your search every time, think of your search zone as a flexible window or a caterpillar moving across the array.The strategy relies on two pointers: left and right.

1. Expand: Move right pointer to the right, adding numbers to your current_sum until it meets or exceeds the target.
2. Shrink: Once you hit the target, your window is valid! Record its size. Now, try to make it even smaller by moving left to the right (and subtracting that element from current_sum). Keep shrinking until the sum drops below the target.
3. Repeat: Keep expanding right and shrinking left until you process the entire array.Because both pointers only ever move forward, every element is looked at at most twice. This gives us a highly efficient $O(n)$ time complexity.

🛠️ Code Implementation (Python)

def minSubArrayLen(target: int, nums: list[int]) -> int:
    # Track the absolute minimum length found
    min_length = float('inf')
    
    current_sum = 0
    left = 0
    
    # Expand the window using the right pointer
    for right in range(len(nums)):
        current_sum += nums[right]
        
        # Shrink the window as long as the condition is met
        while current_sum >= target:
            # Update the shortest window length found so far
            min_length = min(min_length, right - left + 1)
            
            # Remove the leftmost element and move the pointer
            current_sum -= nums[left]
            left += 1
            
    # If min_length was never updated, no valid subarray exists
    return min_length if min_length != float('inf') else 0