[LeetCode] 862. Shortest Subarray with Sum at Least K

 

Problem Statement: 862. Shortest Subarray with Sum at Least K
Category: Prefix Sum, Deque        

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> sum(n);
        int minlen = INT_MAX;
        deque<int> dq;
        for (int i = 0; i < nums.size(); i++) {
            sum[i] = nums[i] + (i - 1 >= 0 ? sum[i - 1] : 0);
            if (sum[i] >= k) {
                minlen = min(minlen, i + 1);
            }
            while (dq.size() and sum[i] - sum[ dq.front() ] >= k) {
                minlen = min(minlen, i - dq.front());
                dq.pop_front();
            }
            while (dq.size() and sum[ dq.back() ] >= sum[i]) {
                dq.pop_back();
            }
            dq.push_back(i);
        }
        return minlen == INT_MAX ? -1 : minlen;
    }
};