Minimum Size Subarray Sum

01 · Question

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is at least target. If there is no such subarray, return 0.

02 · Analysis

Add the rightmost value to the running sum. While the sum is at least target, record the current length before removing the leftmost value. Positive values guarantee that expansion cannot reduce the sum and shrinking cannot increase it. Both pointers advance at most n times: O(n) time, O(1) space. Return 0 when the best-length sentinel is unchanged.

03 · Solution

Reference solution

1def minSubArrayLen(target: int, nums: List[int]) -> int:
2    l = 0
3    cur = 0
4    res = float('inf')
5
6    for r in range(len(nums)):
7        cur += nums[r]
8        while cur >= target:
9            res = min(res, r - l + 1)
10            cur -= nums[l]
11            l += 1
12
13    return 0 if res == float('inf') else res

Most Sales in K Days