#167MediumSliding Window· Shortest Window with Positive Values

Shortest Stretch for a Quota

A courier drives down a street and passes consecutive drop-off points. The number at each point is the weight of parcels waiting there, always a positive integer. To fill one trip, the courier must collect parcels from a **consecutive run of stops** whose total weight is at least `quota`, and wants to visit as few stops as possible. Given `quota` and the array `weights`, return the minimum number of consecutive stops whose weights sum to at least `quota`. If even the whole street does not reach the quota, return `0`.

Input format

`quota`: a positive integer; `weights`: an array of positive integers.

Output format

An integer: the length of the shortest contiguous subarray with sum at least `quota`, or 0 if none exists.

Examples

Input: quota = 7, weights = [2, 3, 1, 2, 4, 3]

Output: 2

The stops [4, 3] weigh 7 and are two stops long. No single stop reaches 7, so 2 is optimal.

Input: quota = 4, weights = [1, 4, 4]

Output: 1

A single stop with weight 4 already meets the quota.

Input: quota = 11, weights = [1, 1, 1, 1, 1, 1, 1, 1]

Output: 0

The whole street weighs only 8, which is less than 11, so no trip is possible.

Constraints

1 <= quota <= 10^9
1 <= weights.length <= 10^5
1 <= weights[i] <= 10^4

#sliding-window
#two-pointers
#prefix-sums
#binary-search