Medium

Minimum Size Subarray Sum

LAB

Given array of positive integers and target, find minimal length subarray with sum >= target. Return 0 if none exists.

FUNCTION SHAPE

→unknown

SOLUTION NOTE

For positive numbers, sliding window is optimal. Prefix sum + binary search works for any array but is slower. Binary search finds the rightmost valid left boundary.

Reveal reference solution +

pythonREFERENCE

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    # Two approaches: prefix sum + binary search, or sliding window

    # Approach 1: Sliding window (better for positive numbers)
    left = 0
    curr_sum = 0
    res = inf

    for right in range(len(nums)):
        curr_sum += nums[right]
        while curr_sum >= target:
            res = min(res, right - left + 1)
            curr_sum -= nums[left]
            left += 1

    return res if res != inf else 0

# Approach 2: Prefix sum + binary search
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    prefix = list(accumulate(nums))
    prefix.append(0)
    res = inf

    for r in range(len(nums)):
        if prefix[r] >= target:
            # Find smallest l where prefix[r] - prefix[l-1] >= target
            # i.e., prefix[l-1] <= prefix[r] - target
            l = bisect_right(prefix, prefix[r] - target)
            res = min(res, r - l + 1)

    return res if res != inf else 0

TimeO(n) sliding window, O(n log n) binary search

SpaceO(1) or O(n)

Open on LeetCode ↗