1
class Solution {
2
 public:
3
  // 2-pointer doesnt work on neg elements
4
  // Using mono deque to solve sliding window
5
  int shortestSubarray(vector<int> &nums, int k) {
6
    int n = nums.size();
7
    int minsize = INT_MAX;
8
    vector<long> prefixsum(n, 0);
9
    deque<int> dq;
10

11
    prefixsum[0] = nums[0];
12
    for (int i = 1; i < n; i++) prefixsum[i] = prefixsum[i - 1] + nums[i];
13

14
    for (int i = 0; i < n; i++) {
15
      if (prefixsum[i] >= k) minsize = min(minsize, i + 1);
16

17
      while (!dq.empty() && prefixsum[i] - prefixsum[dq.front()] >= k) {
18
        minsize = min(minsize, i - dq.front());
19
        dq.pop_front();
20
      }
21

22
      while (!dq.empty() && prefixsum[i] <= prefixsum[dq.back()]) {
23
        dq.pop_back();
24
      }
25

26
      dq.push_back(i);
27
    }
28
    return (minsize == INT_MAX) ? -1 : minsize;
29
  }
30
};