530. Shortest Subarray with Sum at Least K
You are given an integer array nums — the values may be negative — and a positive integer k.
Find the shortest non-empty contiguous subarray whose elements add up to k or more, and return its length. If no contiguous run of elements ever reaches a sum of k, return -1.
The negatives are the whole difficulty: with them, growing a window can shrink its sum, so the classic sliding-window argument falls apart. You will need prefix sums plus something cleverer than two pointers to hit O(n).
Example 1:
Input: nums = [2, -1, 2], k = 3
Output: 3
Explanation: No single element reaches 3 and both length-2 windows sum to 1, but the whole array sums to 2 - 1 + 2 = 3.
Example 2:
Input: nums = [1, 2], k = 4
Output: -1
Explanation: The largest possible sum is 1 + 2 = 3, which never reaches 4.
Example 3:
Input: nums = [1], k = 1
Output: 1
Explanation: The single element already meets the target.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- -10⁵ ≤ nums[i] ≤ 10⁵
- 1 ≤ k ≤ 10⁹
- Prefix sums can exceed 32-bit range — use 64-bit arithmetic.
Hints:
Build prefix sums: prefix[j] − prefix[i] is the sum of the subarray (i..j−1]. You want the largest i < j with prefix[j] − prefix[i] >= k, for every j — that is O(n²) done naively.
Keep candidate start indices in a deque whose prefix values increase from front to back. If prefix[i1] >= prefix[i2] for i1 < i2, index i1 is useless — i2 is both later (shorter subarray) and a smaller value (easier to satisfy). Pop it.
At each j: pop matches off the FRONT (once prefix[j] − prefix[front] >= k, the front can never give a shorter answer later, since later j's are farther away), then pop dominated indices off the BACK, then push j. Each index enters and leaves once — O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [2, -1, 2], k = 3
Expected output: 3