862. Shortest Subarray with Sum at Least K

/*
Refer: https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C++JavaPython-O(N)-Using-Deque
Using prefix array
Time Complexity: O(n)
Space Complexity: O(n)
*/
class Solution {
    public int shortestSubarray(int[] A, int K) {
        if (A == null || A.length == 0) {
            return -1;
        }
        int n = A.length;
        int result = n+1;
        int[] prefixArr = new int[n+1];
        for (int i = 0; i < n; i++) {
            prefixArr[i+1] = prefixArr[i] + A[i];
        }
        Deque<Integer> deque = new LinkedList();
        for (int i = 0; i < n+1; i++) {
            while (!deque.isEmpty() && prefixArr[i] - prefixArr[deque.peekFirst()] >= K) {
                result = Math.min(result, i - deque.pollFirst());
            }
            while (!deque.isEmpty() && prefixArr[i] <= prefixArr[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.addLast(i);
        }
        return result <= n ? result : -1;
    }
}