Minimum Size Subarray Sum

Problem

Given an array nums of positive integers and a positive integer target, return the length of the shortest contiguous subarray whose sum is greater than or equal to target. If no subarray reaches target, return 0.

Two details matter: elements are strictly positive (this is what makes the fast solution work), and you want the minimum length — a reversal of the more common “longest valid window” setup.

Examples

• target = 7, nums = [2, 3, 1, 2, 4, 3] → 2 — [4, 3] sums to 7; no single element reaches 7.
• target = 4, nums = [1, 4, 4] → 1 — a single 4 already meets the target.
• target = 11, nums = [1, 1, 1, 1, 1] → 0 — the whole array sums to 5, so no valid subarray exists.

Constraints

• 1 <= target <= 10^9
• 1 <= len(nums) <= 10^5
• 1 <= nums[i] <= 10^4

O(n²) subarray enumeration is ~5 * 10^9 steps at n = 10^5. The expected solution is O(n); an O(n log n) prefix-sum + binary-search solution is a classic follow-up.

Think about it first

TL;DR

Shrinking sliding window (grow until sum ≥ target, then shrink while it stays ≥) — O(n) time, O(1) space.

Approach 1 — Brute force

For each start index, extend until the sum first reaches target (going further only lengthens the subarray).

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        best = n + 1
        for i in range(n):
            total = 0
            for j in range(i, n):
                total += nums[j]
                if total >= target:
                    best = min(best, j - i + 1)
                    break
        return best if best <= n else 0

Complexity: O(n²) time, O(1) space. At n = 10^5, worst case ~5 * 10^9 additions — the constraints forbid it.

Approach 2 — Sliding window

The insight: with all-positive elements the window sum is strictly monotone in both directions — extending increases it, shrinking decreases it. So as right advances, the shortest qualifying window ending at right starts at a left that never moves backward: grow until the sum qualifies, then shrink from the left while it still qualifies, recording every qualifying length.

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        best = n + 1
        total = 0
        left = 0
        for right, x in enumerate(nums):
            total += x
            while total >= target:               # qualifies: record, then try shorter
                best = min(best, right - left + 1)
                total -= nums[left]
                left += 1
        return best if best <= n else 0

Walkthrough on target = 7, nums = [2, 3, 1, 2, 4, 3]:

Answer: 2 ([4, 3]).

Complexity: left and right each advance at most n times, so O(n) time despite the nested loop; O(1) space.

Approach 3 — Prefix sums + binary search (the follow-up)

The insight: positive elements make the prefix-sum array strictly increasing, so for each start i the smallest end with prefix[j] - prefix[i] >= target can be found by binary search instead of a scan. Worth knowing because it survives even when a problem forces per-start queries.

import bisect
from itertools import accumulate

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        prefix = [0] + list(accumulate(nums))    # prefix[j] = sum of nums[:j], strictly increasing
        best = n + 1
        for i in range(n):
            j = bisect.bisect_left(prefix, prefix[i] + target, i + 1)
            if j <= n:
                best = min(best, j - i)
        return best if best <= n else 0

Complexity: O(n log n) time, O(n) space. Strictly worse than the window here — mention it as the follow-up, reach for it when windows don’t apply.

Common pitfalls

• Count-before-shrink, not shrink-before-count. This is a minimum-length problem: record the length while the window is valid, i.e. inside the shrink loop before dropping nums[left]. Recording after the loop (the longest-window habit) measures an invalid, too-short window.
• Returning n + 1 (or inf) instead of 0 when no window qualifies — remember the sentinel-to-zero conversion at the end.
• Assuming this works with negatives. It doesn’t: a negative element breaks the monotone sum, so shrinking might increase the sum and the frontier argument collapses (that variant needs prefix sums with a monotone deque).
• >= vs >: the target is met at greater than or equal; using > silently misses exact hits like target = 7, window [4, 3].

Pattern takeaway

The mirror image of “longest valid window”: for shortest qualifying window, grow until you qualify, then shrink greedily while you still qualify — and record inside the shrink phase, since there validity holds. The license for all of it is monotonicity of the window aggregate, which here comes from the all-positive guarantee; always check that guarantee before reaching for this template.