0862. Shortest Subarray with Sum at Least K

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k

Description

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Example 1:

**Input:** nums = [1], k = 1
**Output:** 1

Example 2:

**Input:** nums = [1,2], k = 4
**Output:** -1

Example 3:

**Input:** nums = [2,-1,2], k = 3
**Output:** 3

Constraints:

• 1 <= nums.length <= 105

• -105 <= nums[i] <= 105

• 1 <= k <= 109

ac: Monotonic queue

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C++JavaPython-O(N)-Using-Deque/150644

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int len = nums.length;
        int[] prefixSum = new int[len+1];
        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] = prefixSum[i-1] + nums[i-1];
        }
        
        int minLen = len + 1;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(0);
        for (int i = 1; i < prefixSum.length; i++) {
            while (!queue.isEmpty() && prefixSum[i] - prefixSum[queue.peekFirst()] >= k) {
                // Pop the left index, because future subarray must be smaller than current one, thus it's meaningless to start from this left index.
                int subLen = i - queue.pollFirst();
                minLen = Math.min(minLen, subLen);
            }
            
            // Keep an increasing queue. E.g. [0, 4, 10, 7, 4, 5], if prefixSum[i] - prefixSum[4](2nd 4) >= k, then we don't care about (4, 10, 7) index, because we already found smaller length subarray.
            while (!queue.isEmpty() && prefixSum[queue.peekLast()] >= prefixSum[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        
        return minLen == len + 1 ? -1 : minLen;
    }
}

// O(N) time, O(N) space