> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0862-shortest-subarray-with-sum-at-least-k.md).

# 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>

```java
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
```