Problem statement:

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:

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

Solution

public int shortestSubarray(int[] A, int K) {
    int n = A.length + 1;
    int[] preSum = new int[n];
    for (int i = 1; i < n; i++) {
        preSum[i] = A[i - 1] + preSum[i - 1]; // presum[0] = 0
    }
    //keep deque increasing
    Deque<Integer> deque = new ArrayDeque<>();
    int result = n;
    for (int i = 0; i < n; i++) {
        //if presum decreasing poll last
        while (!deque.isEmpty() && preSum[i] <= preSum[deque.peekLast()]) {
            deque.pollLast();
        }
        //if diff >= k calculate result
        while (!deque.isEmpty() && preSum[i] - preSum[deque.peekFirst()] >= K) {
            result = Math.min(result, i - deque.pollFirst());
        }
        deque.addLast(i);
    }
    return result == n ? -1 : result;
}

Time complexity:

O(N)

Space complexity:

O(N)

Approach:

1. Build prefix sum array.
2. Keep dequeue of sums increasing.
3. Check presum[i] - presum[deque.first] ≥ K, then calculate result.