The Shortest Climb Worth Logging

A hiking app splits a trail into segments; gains[i] is the height change in metres over segment i (negative means downhill). A hiker wants to log the shortest run of consecutive segments whose total height change is at least target metres.

Return the number of segments in the shortest such run, or -1 if no run reaches target.

Examples

Input:  gains = [3, -4, 2, 2, -1, 3], target = 5
Output: 4
Explanation: 2 + 2 - 1 + 3 = 6 >= 5, and no run of 3 or fewer segments reaches 5.

Input:  gains = [2, -1, 2], target = 3
Output: 3

Input:  gains = [1, 2], target = 4
Output: -1

Constraints

• 0 <= len(gains) <= 10**5
• -10**4 <= gains[i] <= 10**4
• 1 <= target <= 10**9
• Target: O(n) time. Because of the downhill segments, a window that only grows on the right and shrinks on the left does not work.

Goals

• Rewrite stretch sums as differences of running totals
• Keep candidate start points in a deque with increasing running totals
• Discard candidates from both ends of the deque, each for its own reason