#211HardMonotonic Queue· Deque over Prefix Sums with Negative Values

Shortest Subarray with Budget

A solar farm logs the net energy change of every hour as an integer: positive when the panels charged the battery, negative when the battery was drained. An engineer wants the **shortest stretch of consecutive hours** whose total net change is **at least** `target`. Return the length of the shortest non-empty contiguous subarray of `nums` whose sum is at least `target`, or `-1` if no such subarray exists. Values can be negative, so extending a window does not always increase its sum, and the classic "grow and shrink" two-pointer method does not work.

Input format

`nums`: the hourly net changes. `target`: the required total.

Output format

The length of the shortest qualifying subarray, or -1.

Examples

Input: nums = [1], target = 1

Output: 1

The single element 1 reaches the target of 1, so the shortest length is 1.

Input: nums = [2, -1, 2], target = 3

Output: 3

Only the whole array adds up to at least 3 (2 - 1 + 2 = 3), so the answer is 3.

Input: nums = [1, 2], target = 4

Output: -1

The total of all elements is 3, below 4, so no stretch qualifies and the answer is -1.

Constraints

1 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5
1 <= target <= 10^9

#monotonic-deque
#prefix-sums
#sliding-window
#subarray
#negative-numbers