Minimum Size Subarray Sum

3Sum

Number of Provinces

Find the shortest contiguous subarray whose sum reaches a target.

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

## Example
```
Input: {"target":7,"nums":[2,3,1,2,4,3]}
Output: 2
```

**Constraints**
- 1 <= target <= 1000000000
- 1 <= nums.length <= 100000
- 1 <= nums[i] <= 100000

**Follow-up**
Can you also solve it in O(n log n) with binary search on prefix sums?

- Find the length of the shortest contiguous run of `nums` whose sum is >= `target`, or 0 if no run reaches it.
- All values are positive — that constraint is what makes a sliding window valid here instead of needing prefix sums with binary search.

Understand the Goal

- Variable-size sliding window with two pointers: because every element is positive, the running window sum is monotonic in both directions — growing the window (moving `right`) can only increase the sum, and shrinking it (moving `left`) can only decrease it.
- That monotonicity is exactly what breaks with negative values: shrinking the window could increase the sum instead (removing a negative number raises the total), so the greedy "shrink while sum is big enough" rule would no longer be safe, and you'd need a different technique (e.g. prefix sums with a monotonic deque, since binary search alone doesn't work either once prefix sums stop being non-decreasing).

Choose the Core Pattern

- Expand the window by moving `right` across every index once, adding `nums[right]` to a running `windowSum`.
- After each addition, while `windowSum >= target`, the current window is a valid candidate: record its length if it's the best seen so far, then shrink from the left by subtracting `nums[left]` and advancing `left` — shrinking is always safe to attempt again immediately, since the sum only goes down and might still satisfy `>= target`.
- Because `left` only ever advances and never resets backward, each index is added to the sum once and removed at most once, giving O(n) total work despite the nested loop.

Build the Algorithm

- No subarray reaches `target` (e.g. all values are 1 and `target` exceeds the total sum): the inner while loop never triggers, and the best-length sentinel must be recognized and converted to 0 in the return value.
- The entire array is required (e.g. `target` equals the whole array's sum, achieved only once at the end): the window must be allowed to grow all the way to `right == len(nums) - 1` before it first becomes valid.
- A single element already meets `target`: the window shrinks immediately back down to length 1 on the same iteration it became valid.