Shortest Subarray with Sum at Least K (with Negatives)

Problem Statement

Given an array of integers nums (which can contain negative numbers) and an integer k, return the length of the shortest non-empty contiguous subarray with a sum of at least k.

If no such subarray exists, return -1.

Constraints

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5
• 1 <= k <= 10^9
• Expected: O(n) time

Examples

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

Output: 3

Explanation: The entire array [2, -1, 2] sums to 3, which is the shortest subarray with sum >= 3.

Input: nums = [1], k = 1

Output: 1

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

Output: -1

Explanation: No subarray sums to at least 4.

Input: nums = [84, -37, 32, 40, 95], k = 167

Output: 3

Explanation: Subarray [32, 40, 95] sums to 167.

Why This is Hard

The presence of negative numbers makes the standard sliding window approach invalid. You can't simply shrink the window from the left because removing an element might decrease or increase the sum unpredictably.

What the Interviewer Expects

1. Why basic sliding window fails — with negatives, the sum isn't monotonically increasing as you expand the window.
2. Prefix sum insight — subarray sum from i to j = prefix[j+1] - prefix[i]. You need prefix[j] - prefix[i] >= k with minimum j - i.
3. Monotonic deque on prefix sums:
   • Maintain a deque of indices where prefix sums are increasing
   • For each j, pop from front while prefix[j] - prefix[front] >= k (found a valid subarray, try shorter)
   • Pop from back while prefix[j] <= prefix[back] (current prefix is smaller, previous is useless)
4. Time complexity: O(n) — each index enters and leaves the deque at most once.
5. Why the deque works: it maintains the smallest prefix sums we haven't used yet, in order. Once a prefix sum produces a valid answer, we discard it (can't do better with a later j).

Follow-ups

1. If all numbers are positive, how does this simplify? (Standard sliding window works)
2. Can you solve this with binary search + prefix sums in O(n log n)? When would you choose that over the deque approach?
3. What if you need the actual subarray (not just the length)?
4. What if the problem asks for "exactly k" instead of "at least k"?
5. How does this relate to the "Sliding Window Maximum" problem? (Both use monotonic deques)