Shortest Subarray with Sum at Least K

Prefix Sums, problem 7 of 7

Shortest Subarray with Sum at Least K

Hard

LC #862

prefix summonotonic dequesliding window

Not attempted yet

Given an integer array nums (which may contain negative numbers) and a positive integer k, return the length of the shortest non-empty contiguous subarray whose sum is at least k. Return -1 if there is none.

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

Only the whole array reaches 3.

Constraints

  • 1 ≤ len(nums) ≤ 10⁵
  • -10⁵ ≤ nums[i] ≤ 10⁵
  • 1 ≤ k ≤ 10⁹

Python

Loading draft…

Test results

9 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 6 hidden

Run examples, then submit all tests.