> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/sub-array-problems/10.-shortest-subarray-with-sum-at-least-k-negative-numbers.md).

# 13. Shortest Subarray with Sum at Least K (Negative Numbers)

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

## Solution: (Prefix Sum + Deque)

**Explanation:** 

```cpp
class Solution
{
public:
    int shortestSubarray(vector<int> &A, int k)
    {

        int n = A.size();
        vector<int> ps(n);
        deque<int> d;
        ps[0] = A[0];

        for (int i = 1; i < n; i++)
        {
            ps[i] = A[i] + ps[i - 1];
        }

        int maxLen = n + 1;
        
        for (int i = 0; i < n; i++)
        {

            if (ps[i] >= k)
            {
                maxLen = min(maxLen, i + 1);
            }

            while (d.size() > 0 && ps[i] - ps[d.front()] >= k)
            {
                int len = i - d.front();
                maxLen = min(maxLen, len);
                d.pop_front();
            }

            while (d.size() > 0 && ps[i] <= ps[d.back()])
            {
                d.pop_back();
            }

            d.push_back(i);
        }

        if (maxLen == n + 1)
        {
            return -1;
        }

        return maxLen;
    }
};
```

**Time Complexity: O(n)**