Shortest Subarray with Sum at Least K
Hard · Stack & Strings · Array · Prefix Sum · Queue · Monotonic Queue · Sliding Window
Problem
Given an integer array nums, which may contain negative numbers, and an integer k, return the length of the shortest non-empty contiguous subarray whose sum is at least k. If no such subarray exists, return -1.
Examples
Input: nums = [3,-2,5,1], k = 6 Output: 2
[5,1] sums to 6, and no single element reaches 6.
Input: nums = [1,2], k = 4 Output: -1
The whole array only sums to 3.
Input: nums = [4,-1,2,-5,7], k = 7 Output: 1
The single element 7 is enough.
Constraints
- 1 <= len(nums) <= 10^5
- -10^5 <= nums[i] <= 10^5
- 1 <= k <= 10^9
Approaches
- Baseline: every start, shortest end first — time O(n²), space O(n)
Follow-up
If all values were positive, a plain sliding window would do (the problem Minimum Size Subarray Sum). For the longest subarray with sum at least k, keep the prefix minima from the left on a stack and scan ends from the right instead (see the use case "Longest subarray with sum at least k").
Related problems
Start free on Cariara · Coding problems · System design studio
