Shortest Subarray with Sum ≥ K [Hard] — Monotonic Deque on Prefix

Problem Statement

Return the length of the shortest non-empty subarray with sum ≥ k. Array may have negative numbers. Return -1 if none.

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

Intuition

Compute prefix sums. Maintain a monotone increasing deque of prefix sum indices. For each i, pop from front while prefix[i]-prefix[dq.front()]>=k (record min length). Pop from back while prefix[dq.back()]>=prefix[i].

Solutions

C++

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

Python

from collections import deque

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

Complexity

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