All problems

Shortest Subarray with Sum at Least K

Hard · monotonic deque

You are given a list of integers nums, which may contain negative numbers and zeros, and a positive integer k.

Look at the contiguous, non-empty parts of nums: runs of neighbouring elements. Return the length of the shortest part whose elements add up to at least k.

If no part adds up to at least k, return -1.

Examples

Example 1

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

Output: 3

Only the whole list reaches 3: 2 + (-1) + 2 = 3. Every shorter part adds up to 2 or less.

Example 2

Input: nums = [1, 4, 6], k = 5

Output: 1

The single element 6 is already at least 5.

Example 3

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

Output: -1

The whole list adds up to 3, so no part reaches 4.

Constraints