862. Shortest Subarray with Sum at Least K

Version #1 PrefixSum + Deque -> Two Pointers
Time O(n)
Space O(n)

76.40 %
class Solution {
    public int shortestSubarray(int[] A, int K) {
        int[] prefixSum = new int[A.length + 1];
        for (int i = 1; i <= A.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + A[i - 1];
        }
        // sum[i,j) -> prfixSum[j] - prefixSum[i] >= K -> prefixSum[i] <= prefixSum[j] - K
        // Guarantee that all subsequent i won't work once it violate the criteria
        int min = Integer.MAX_VALUE;
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(0);
        for (int j = 1; j <= A.length; j++) {
            while (!deque.isEmpty() && prefixSum[j] < prefixSum[deque.peekLast()]) {
                deque.removeLast();
            }
            deque.addLast(j);
         
            while (!deque.isEmpty() && prefixSum[deque.peekFirst()] <= prefixSum[j] - K) {
                min = Math.min(min, j - deque.removeFirst());
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}