Shortest Subarray Reaching Sum

Gold

10000ms500MB

You are given an integer array nums (values may be negative) and a positive integer k.

Return the length of the shortest non-empty contiguous subarray of nums whose sum is at least k, or -1 if no such subarray exists.

Examples

Example 1

Input: nums = [1], k = 1
Output: 1

Example 2

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

Example 3

Input: nums = [2,-1,2], k = 3
Output: 3
Explanation: Only the whole array reaches sum 3, since the negative middle element must be bridged.

Constraints

$1 \leq$ nums.length $\leq 10^5$
$-10^5 \leq$ nums[i] $\leq 10^5$
$1 \leq k \leq 10^9$

Examples

Example 1

Input

nums = [1]

k = 1

Output

Example 2

Input

nums = [1, 2]

k = 4

Output

-1

Example 3

Input

nums = [2, -1, 2]

k = 3

Output

Loading editor...

Click "Run" to test with sample cases or "Submit" to run all tests.

Shortest Subarray Reaching Sum

Gold

10000ms500MB

You are given an integer array nums (values may be negative) and a positive integer k.

Return the length of the shortest non-empty contiguous subarray of nums whose sum is at least k, or -1 if no such subarray exists.

Examples

Example 1

Input: nums = [1], k = 1
Output: 1

Example 2

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

Example 3

Input: nums = [2,-1,2], k = 3
Output: 3
Explanation: Only the whole array reaches sum 3, since the negative middle element must be bridged.

Constraints

$1 \leq$ nums.length $\leq 10^5$
$-10^5 \leq$ nums[i] $\leq 10^5$
$1 \leq k \leq 10^9$

Examples

Example 1

Input

nums = [1]

k = 1

Output

Example 2

Input

nums = [1, 2]

k = 4

Output

-1

Example 3

Input

nums = [2, -1, 2]

k = 3

Output

Loading editor...

Click "Run" to test with sample cases or "Submit" to run all tests.