Shortest Subarray with Sum at Least K — Deque + Prefix Sum

# Python
from collections import deque
def shortestSubarray(nums, k):
    n = len(nums)
    prefix = [0]*(n+1)
    for i in range(n): prefix[i+1] = prefix[i]+nums[i]
    dq = deque()
    ans = float('inf')
    for j in range(n+1):
        while dq and prefix[j]-prefix[dq[0]] >= k:
            ans = min(ans, j-dq.popleft())
        while dq and prefix[dq[-1]] >= prefix[j]:
            dq.pop()
        dq.append(j)
    return ans if ans < float('inf') else -1

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