Minimum Size Subarray Sum Algorithm

Given an array of positive integers and a target, find the smallest contiguous subarray whose sum is at least the target. If no such subarray exists, return 0.

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
The subarray [4,3] has the minimal length.

The intuition

Sliding window. Expand the right side to grow the sum. Once the sum meets or exceeds the target, shrink from the left to find the smallest valid window.

Every time the window is valid, record its length if it's the smallest so far. Then shrink and keep going.

The code

var minSubArrayLen = function(target, nums) {
    let left = 0;
    let sum = 0;
    let minLength = Infinity;

    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];

        while (sum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }

    return minLength === Infinity ? 0 : minLength;
};

How it works

The right pointer expands the window by adding elements to the sum. Once the sum hits the target, the inner while loop contracts the window from the left, subtracting elements and updating the minimum length. This ensures you find the tightest fit.

Complexity

• Time: O(n) — each element is added and removed at most once.
• Space: O(1) — just pointers and a running sum.

Trade-offs

The sliding window only works because all numbers are positive (the sum always grows as you expand). If the array had negative numbers, you'd need a different approach — prefix sums with binary search, which bumps time to O(n log n).