LeetCode 209: Minimum Size Subarray Sum

Problem Restatement

We are given:

target
nums

nums is an array of positive integers.

We need to find the minimal length of a contiguous subarray whose sum is greater than or equal to target.

If no such subarray exists, return 0.

The official statement asks for the minimal length of a subarray whose sum is at least target, with constraints 1 <= target <= 10^9, 1 <= nums.length <= 10^5, and 1 <= nums[i] <= 10^4.

Input and Output

Example function shape:

def minSubArrayLen(target: int, nums: list[int]) -> int:
    ...

Examples

Example 1:

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

The subarray:

[4, 3]

has sum:

7

Its length is 2.

No shorter subarray reaches 7.

Answer:

2

Example 2:

target = 4
nums = [1, 4, 4]

The single element subarray:

[4]

already reaches the target.

Answer:

1

Example 3:

target = 11
nums = [1, 1, 1, 1, 1, 1, 1, 1]

The total sum is only 8, so no subarray can reach 11.

Answer:

0

First Thought: Check Every Subarray

The direct method is to try every start index.

For each start index, extend the subarray to the right until the sum reaches target.

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        best = n + 1

        for left in range(n):
            total = 0

            for right in range(left, n):
                total += nums[right]

                if total >= target:
                    best = min(best, right - left + 1)
                    break

        return 0 if best == n + 1 else best

This works, but it can be too slow.

Problem With Brute Force

There can be up to 10^5 numbers.

Checking all subarrays may take quadratic time:

O(n^2)

That is too large for this input size.

We need to use the fact that all numbers are positive.

Key Insight: Sliding Window

Because every number in nums is positive:

• Expanding the window to the right always increases the sum.
• Shrinking the window from the left always decreases the sum.

This makes a sliding window possible.

We maintain a window:

nums[left:right + 1]

with its current sum.

When the sum is too small, expand right.

When the sum is large enough, try shrinking from the left to make the window shorter.

Algorithm

1. Set left = 0.
2. Set total = 0.
3. Set best = infinity.
4. Scan right from 0 to len(nums) - 1:
   • Add nums[right] to total.
   • While total >= target:
     • Update the best answer with the current window length.
     • Remove nums[left] from total.
     • Move left forward.
5. Return 0 if no valid window was found. Otherwise return best.

Walkthrough

Use:

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

Start:

left = 0
total = 0
best = infinity

Move right forward:

Best length found:

2

Correctness

The algorithm considers every possible right endpoint exactly once.

For each right, it expands the window by adding nums[right].

Once the current window sum is at least target, the algorithm repeatedly removes elements from the left while the window remains valid. During this process, every valid window ending at the current right and starting from the current left positions is checked before it becomes invalid.

Because all numbers are positive, moving left forward can only decrease the sum. Therefore, once removing nums[left] makes the sum too small, no further shrink for that same right can produce a valid window.

The algorithm never misses a shorter valid subarray because every left pointer position is advanced only after the corresponding window has been tested while valid.

Thus the minimum recorded length is exactly the shortest contiguous subarray whose sum is at least target.

Complexity

Although there is a nested while loop, the total number of left-pointer moves over the whole algorithm is at most n.

Implementation

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        left = 0
        total = 0
        best = n + 1

        for right, value in enumerate(nums):
            total += value

            while total >= target:
                best = min(best, right - left + 1)
                total -= nums[left]
                left += 1

        if best == n + 1:
            return 0

        return best

Code Explanation

Initialize the left side of the window:

left = 0

Track the current window sum:

total = 0

Use an impossible value as the initial best answer:

best = n + 1

Expand the window by moving right:

for right, value in enumerate(nums):
    total += value

When the window reaches the target, update the answer:

best = min(best, right - left + 1)

Then shrink from the left:

total -= nums[left]
left += 1

If no valid window was found:

if best == n + 1:
    return 0

Otherwise return the best length:

return best

Alternative: Prefix Sum and Binary Search

The follow-up asks for an O(n log n) solution. Since all numbers are positive, prefix sums are strictly increasing.

Build:

prefix[i] = sum(nums[0:i])

For each start index i, we need the smallest index j such that:

prefix[j] - prefix[i] >= target

which means:

prefix[j] >= prefix[i] + target

We can find j using binary search.

from bisect import bisect_left

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        prefix = [0]

        for num in nums:
            prefix.append(prefix[-1] + num)

        best = n + 1

        for i in range(n):
            need = prefix[i] + target
            j = bisect_left(prefix, need)

            if j <= n:
                best = min(best, j - i)

        return 0 if best == n + 1 else best

The sliding window version is better because it runs in O(n) time.

Testing

def run_tests():
    s = Solution()

    assert s.minSubArrayLen(7, [2,3,1,2,4,3]) == 2
    assert s.minSubArrayLen(4, [1,4,4]) == 1
    assert s.minSubArrayLen(11, [1,1,1,1,1,1,1,1]) == 0
    assert s.minSubArrayLen(15, [1,2,3,4,5]) == 5
    assert s.minSubArrayLen(6, [10,2,3]) == 1
    assert s.minSubArrayLen(5, [2,3,1,1,1]) == 2

    print("all tests passed")

run_tests()