# LeetCode 209: Minimum Size Subarray Sum

## Problem Restatement

We are given:

```python
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

| Item | Meaning |
|---|---|
| Input | Integer `target` and integer array `nums` |
| Output | Minimum length of a valid contiguous subarray |
| Valid subarray | Sum is greater than or equal to `target` |
| Return `0` | No valid subarray exists |
| Key constraint | All numbers are positive |

Example function shape:

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

## Examples

Example 1:

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

The subarray:

```python
[4, 3]
```

has sum:

```python
7
```

Its length is `2`.

No shorter subarray reaches `7`.

Answer:

```python
2
```

Example 2:

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

The single element subarray:

```python
[4]
```

already reaches the target.

Answer:

```python
1
```

Example 3:

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

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

Answer:

```python
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`.

```python
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:

```text
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:

```text
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:

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

Start:

```text
left = 0
total = 0
best = infinity
```

Move `right` forward:

| Window | Sum | Action |
|---|---:|---|
| `[2]` | 2 | Too small |
| `[2,3]` | 5 | Too small |
| `[2,3,1]` | 6 | Too small |
| `[2,3,1,2]` | 8 | Valid, length 4 |
| `[3,1,2]` | 6 | After removing 2, too small |
| `[3,1,2,4]` | 10 | Valid, length 4 |
| `[1,2,4]` | 7 | Valid, length 3 |
| `[2,4]` | 6 | After removing 1, too small |
| `[2,4,3]` | 9 | Valid, length 3 |
| `[4,3]` | 7 | Valid, length 2 |
| `[3]` | 3 | After removing 4, too small |

Best length found:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each pointer moves from left to right at most once |
| Space | `O(1)` | Only counters and pointers are used |

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

## Implementation

```python
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:

```python
left = 0
```

Track the current window sum:

```python
total = 0
```

Use an impossible value as the initial best answer:

```python
best = n + 1
```

Expand the window by moving `right`:

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

When the window reaches the target, update the answer:

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

Then shrink from the left:

```python
total -= nums[left]
left += 1
```

If no valid window was found:

```python
if best == n + 1:
    return 0
```

Otherwise return the best length:

```python
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:

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

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

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

which means:

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

We can find `j` using binary search.

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `7, [2,3,1,2,4,3]` | Standard example |
| `4, [1,4,4]` | One element reaches target |
| `11, [1,1,1,1,1,1,1,1]` | No valid subarray |
| `15, [1,2,3,4,5]` | Whole array is needed |
| `6, [10,2,3]` | First element already enough |
| `5, [2,3,1,1,1]` | Shortest window appears early |