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

Problem Statement

Return the length of the shortest, non-empty, contiguous subarray with sum ≥ K. Return -1 if no such array exists. Array may have negative numbers.

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

Intuition

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

Solutions

C++

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 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)