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:

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)