Shortest Subarray with Sum at Least K

hard prefix sum deque monotonic queue

Problem

Given an integer array nums 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. Values may be negative, so a plain sliding window does not work.

Inputnums = [2, -1, 2], k = 3

Output3

The whole array sums to 3; no shorter subarray reaches 3.

nums (comma-separated)

from collections import deque

def shortest_subarray(nums, k):
    n = len(nums)
    P = [0] * (n + 1)
    for i in range(n):
        P[i + 1] = P[i] + nums[i]
    dq, ans = deque(), n + 1
    for y in range(n + 1):
        while dq and P[y] - P[dq[0]] >= k:
            ans = min(ans, y - dq.popleft())
        while dq and P[dq[-1]] >= P[y]:
            dq.pop()
        dq.append(y)
    return ans if ans <= n else -1

function shortestSubarray(nums, k) {
  const n = nums.length, P = [0];
  for (let i = 0; i < n; i++) P.push(P[i] + nums[i]);
  const dq = [];           // indices, P increasing
  let ans = n + 1;
  for (let y = 0; y <= n; y++) {
    while (dq.length && P[y] - P[dq[0]] >= k)
      ans = Math.min(ans, y - dq.shift());
    while (dq.length && P[dq[dq.length - 1]] >= P[y])
      dq.pop();
    dq.push(y);
  }
  return ans <= n ? ans : -1;
}

int shortestSubarray(int[] nums, int k) {
    int n = nums.length;
    long[] P = new long[n + 1];
    for (int i = 0; i < n; i++) P[i + 1] = P[i] + nums[i];
    Deque<Integer> dq = new ArrayDeque<>();
    int ans = n + 1;
    for (int y = 0; y <= n; y++) {
        while (!dq.isEmpty() && P[y] - P[dq.peekFirst()] >= k)
            ans = Math.min(ans, y - dq.pollFirst());
        while (!dq.isEmpty() && P[dq.peekLast()] >= P[y])
            dq.pollLast();
        dq.addLast(y);
    }
    return ans <= n ? ans : -1;
}

int shortestSubarray(vector<int>& nums, int k) {
    int n = nums.size();
    vector<long long> P(n + 1, 0);
    for (int i = 0; i < n; i++) P[i + 1] = P[i] + nums[i];
    deque<int> dq; int ans = n + 1;
    for (int y = 0; y <= n; y++) {
        while (!dq.empty() && P[y] - P[dq.front()] >= k)
            ans = min(ans, y - dq.front()), dq.pop_front();
        while (!dq.empty() && P[dq.back()] >= P[y])
            dq.pop_back();
        dq.push_back(y);
    }
    return ans <= n ? ans : -1;
}

Explanation

Because the numbers can be negative, a plain sliding window breaks. Instead we use prefix sums plus a monotonic deque of candidate left endpoints to find the shortest subarray with sum at least k in one pass.

First build P, where P[y] is the sum of the first y values. A subarray from i to y has sum P[y] - P[i], so we want the smallest y - i with P[y] - P[i] >= k.

For each y we do two things. First, while the front of the deque satisfies P[y] - P[dq[0]] >= k, we record the length and pop the front — no later y needs that index since this y is the closest. Second, while the back has P[dq[-1]] >= P[y], we pop the back, because a larger-or-equal prefix later in position can never be a better left endpoint than y. Then we push y.

These two rules keep the deque's P values increasing, so the best candidate is always at the front. Example: nums = [2,-1,2], k = 3 gives P = [0,2,1,3]; only P[3] - P[0] = 3 >= 3 works, a length of 3.

Each index is pushed and popped at most once, so the whole search is O(n).

Time: O(n) Space: O(n)