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).

def minSubArrayLen(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

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 the window until the sum qualifies, then shrink from the left while it still qualifies, recording every qualifying length.

def minSubArrayLen(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)

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. This approach still works when a problem forces per-start queries.

import bisect
from itertools import accumulate

def minSubArrayLen(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 sliding window here; use it only when the window approach doesn’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 the shortest qualifying window, grow until you qualify, then shrink greedily while you still qualify, and record the length inside the shrink phase where validity holds. What licenses this is monotonicity of the window sum, which here comes from the all-positive guarantee. Confirm that guarantee before reaching for this template.