Shortest Subarray With Sum At Least K (With Negatives)

Problem

Given an array that may contain negative numbers, and an integer k, find the length of the shortest contiguous subarray with a sum of at least k. Return -1 if none exists.

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

Python Solution

from collections import deque

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

C++ Solution

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

Java Solution

class Solution {
    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> dq = new ArrayDeque<>();
        int best = n + 1;
        for (int i = 0; i <= n; i++) {
            while (!dq.isEmpty() && prefix[i] - prefix[dq.peekFirst()] >= k) {
                best = Math.min(best, i - dq.pollFirst());
            }
            while (!dq.isEmpty() && prefix[dq.peekLast()] >= prefix[i]) dq.pollLast();
            dq.addLast(i);
        }
        return best <= n ? best : -1;
    }
}

Complexity

Time: O(n) — every prefix index is pushed and popped from the deque at most once. Space: O(n) for the prefix sum array and the deque. This needs a monotonic deque over prefix sums, not a simple two-pointer window, because negative numbers break the assumption that shrinking a window always decreases its sum.