Shortest Subarray with Sum at Least K

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

Example 1:

Input: A = [1], K = 1
Output: 1

Example 2:

Input: A = [1,2], K = 4
Output: -1

Example 3:

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

Note:

1. 1 <= A.length <= 50000

2. -10 ^ 5 <= A[i] <= 10 ^ 5

3. 1 <= K <= 10 ^ 9

class Solution {
    public int shortestSubarray(int[] arr, int K) {
        int N = arr.length, res = N + 1;
        int[] prefix = new int[N + 1];
        for (int i = 0; i < N; i++)
            prefix[i + 1] = prefix[i] + arr[i];
        // Increasing Deque
        Deque<Integer> DQ = new ArrayDeque<>();
        for (int i = 0; i < N + 1; i++) {
            // Finding the sub array from the start which can be reduced from current sum
            // and still maintain >=k sum
            while (DQ.size() > 0 && prefix[i] - prefix[DQ.getFirst()] >= K)
                res = Math.min(res, i - DQ.pollFirst());
            // Maintain increasing DQ from left -> right
            while (DQ.size() > 0 && prefix[i] <= prefix[DQ.getLast()])
                DQ.pollLast();
            DQ.addLast(i);
        }
        return res <= N ? res : -1;
    }
}