Shortest Subarray with Sum at Least K

Problem

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 <= 10^5
-10^5 <= nums[i] <= 10^5
1 <= k <= 10^9

Solution

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        Deque<long[]> dq = new ArrayDeque<>();
        dq.offer(new long[] {-1, 0});
        int i = 0;
        long curSum = 0;
        int res = Integer.MAX_VALUE;
        while (i < nums.length) {
            curSum += nums[i];
            while (!dq.isEmpty() && dq.peekFirst()[1] <= curSum - k) {
                res = Math.min(res, (int) (i - dq.pollFirst()[0]));
            }
            while (!dq.isEmpty() && dq.peekLast()[1] >= curSum) {
                dq.pollLast();
            }
            dq.offerLast(new long[] {i, curSum});
            i++;
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

Explain:

nope.

Complexity:

Time complexity : O(n).
Space complexity : O(n).