Shortest Subarray with Sum at Least K

Share

Find length of shortest subarray with sum at least K (can have negatives).

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

Solution Approach

Prefix sums with monotonic deque. For each i, find last j where prefix[i]-prefix[j] >= K.

  • Compute prefix sums
  • Maintain increasing deque of indices
  • For each i: while prefix[i]-prefix[deque.front] >= K record min and pop front
  • While prefix[i] <= prefix[deque.back]: pop back (maintain increasing)
  • Push i to deque
Java
public int shortestSubarray(int[] nums, int k) {
    int n = nums.length;
    long[] prefix = new long[n + 1];
    for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + nums[i];
    Deque<Integer> deque = new ArrayDeque<>();
    int min = n + 1;
    for (int i = 0; i <= n; i++) {
        while (!deque.isEmpty() && prefix[i] - prefix[deque.peekFirst()] >= k)
            min = Math.min(min, i - deque.pollFirst());
        while (!deque.isEmpty() && prefix[i] <= prefix[deque.peekLast()])
            deque.pollLast();
        deque.addLast(i);
    }
    return min == n + 1 ? -1 : min;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)