862. 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.

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

// O(nlogn) Min Heap
int shortestSubarray(vector<int>& A, int K) { // time: O(nlogn); space: O(n)
    int n = A.size(), res = numeric_limits<int>::max(), sum = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    for (int i = 0; i < n; ++i) {
        sum += A[i];
        if (sum >= K) res = min(res, i + 1);
        while (!pq.empty() && sum - pq.top().first >= K) {
            res = min(res, i - pq.top().second);
            pq.pop();
        }
        pq.push({sum, i});
    }
    return res == numeric_limits<int>::max() ? -1 : res;
}

// O(n) Deque Solution
int shortestSubarray(vector<int>& A, int K) { // time: O(n); space: O(n)
    int n = A.size(), res = numeric_limits<int>::max();
    deque<int> dq;
    vector<int> sums(n + 1);
    for (int i = 1; i <= n; ++i) sums[i] = sums[i - 1] + A[i - 1];
    for (int i = 0; i <= n; ++i) {
        while (!dq.empty() && sums[i] - sums[dq.front()] >= K) {
            res = min(res, i - dq.front());
            dq.pop_front();
        }
        while (!dq.empty() && sums[i] <= sums[dq.back()]) dq.pop_back();
        dq.push_back(i);
    }
    return res == numeric_limits<int>::max() ? -1 : res;
}