nikunjsoni

862

Apr 9th, 2021
92
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int shortestSubarray(vector<int>& A, int K) {
  4.         int ans, sz=A.size();
  5.         deque<int> q;
  6.         int presum[sz+1];
  7.         ans = sz+1;
  8.         presum[0] = A[0];
  9.         for(int i=0; i<sz; i++){
  10.             if(i) presum[i] = presum[i-1] + A[i];
  11.             if(presum[i] >= K) ans = min(ans, i+1);
  12.            
  13.             while(q.size()>0 && presum[q.front()] + K <= presum[i]){
  14.                 ans = min(ans, i-q.front());
  15.                 q.pop_front();
  16.             }
  17.             while(q.size()>0 && presum[q.back()] >= presum[i])
  18.                 q.pop_back();
  19.             q.push_back(i);
  20.         }
  21.         if(ans == sz+1) ans = -1;
  22.         return ans;
  23.     }
  24. };
RAW Paste Data