Minimum Size Subarray Sum

Intuition

Since all values are positive, once a window meets the target there is no reason to keep extra elements on the left, they only make the window longer. So push the right edge forward to build up the sum, and the moment the sum is large enough, pull the left edge in as far as possible while the target is still satisfied. Each element enters and leaves the window at most once, giving a linear scan.

Algorithm walkthrough

1. 1Keep a left pointer, a running sum, and a best-length tracker set to a value larger than any real window.
2. 2Move the right pointer across the array, adding each visited value to the running sum.
3. 3While the running sum is at least the target, update the best length with the current window width, then subtract the left element and advance the left pointer.
4. 4Continue until the right pointer reaches the end of the array.
5. 5If the best length was never improved, return 0; otherwise return the best length found.

Implementation

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        total = 0
        best = len(nums) + 1
        for right in range(len(nums)):
            total += nums[right]
            while total >= target:
                best = min(best, right - left + 1)
                total -= nums[left]
                left += 1
        return 0 if best == len(nums) + 1 else best

Intuition

The cumulative sum array is strictly increasing because all values are positive. For a fixed start, the shortest valid window ends at the first position where the cumulative sum reaches the start's prefix plus the target. Since the prefix array is sorted, that first position can be located with binary search, trading the pure linear scan for an O(n log n) method that is handy when you already need prefix sums for other queries.

Algorithm walkthrough

1. 1Construct a prefix array where prefix[i] holds the sum of the first i elements.
2. 2For each start index i, compute the threshold prefix[i] + target that the window's end must reach.
3. 3Binary-search the prefix array (over indices greater than i) for the first entry that is at least the threshold.
4. 4If such an index exists, its distance from i is a candidate window length; keep the smallest candidate seen.
5. 5Return 0 if no candidate was ever found, otherwise the smallest length.

Implementation

import bisect

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        best = n + 1
        for i in range(n):
            need = prefix[i] + target
            j = bisect.bisect_left(prefix, need, i + 1)
            if j <= n:
                best = min(best, j - i)
        return 0 if best == n + 1 else best