DSA problem
Shortest Subarray with Sum at Least K
Given an integer array nums and an integer k, return the length of the shortest non-empty contiguous subarray of nums with a sum of at least k. If there is no such subarray, return -1.
When nums contains only non-negative integers, a simple two-pointer sliding window suffices: grow until the sum hits k, then shrink. But here nums can contain negatives, which breaks the monotonicity that the basic two-pointer technique relies on (adding an element can decrease the sum, so we cannot greedily shrink from the left).
The clean optimal solution converts the problem to one over the prefix-sum array P, where P[i] = nums[0] + nums[1] + … + nums[i - 1]. A subarray sum from index l to r - 1 equals P[r] - P[l], and we want P[r] - P[l] >= k with the smallest r - l. Equivalently: for each r, find the largest index l < r with P[l] <= P[r] - k and l not too far in the past.
The trick is a monotonic increasing deque of indices into P. As we scan r from 0 to n, we (1) shrink from the front while P[r] - P[deque.front] >= k, updating the best length and popping the front (because any later r with that front would give a longer answer); (2) shrink from the back while P[r] <= P[deque.back] (a smaller, later prefix sum dominates an older, larger one for all future queries); (3) push r. The total work is O(n) time and O(n) space.
Examples
nums = [1], k = 11nums = [1,2], k = 4-1nums = [2,-1,2], k = 33Constraints
- 1 <= nums.length <= 10^5
- -10^5 <= nums[i] <= 10^5
- 1 <= k <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.