> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/hashmap-and-hashset-and-sliding-window/shortest-subarray-with-sum-at-least-k.md).

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

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`

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