Untitled
plain_text
a month ago
1.5 kB
0
Indexable
Never
#include<queue> /* The first for loop processes the first window of size k separately from the rest of the windows because it sets up the initial state of the queue q. The queue q is used to keep track of the indices of negative numbers in the current window. After processing the first window, the queue contains the indices of all negative numbers in the first window. The second for loop then processes the rest of the windows by sliding the window one position at a time and updating the queue accordingly. This approach allows us to process each window in constant time, resulting in an overall time complexity of O(n) for processing all windows */ vector<int> firstNegative(vector<int> arr, int n, int k) { queue<int> q; //stores index of negative numbers vector<int>ans; /* first procees k windows and then process n-k windoes */ for(int i=0;i<k;i++){ //1st k windows if(arr[i]<0) q.push(i); } //we are clsijg the lopp here so we can get some residual indexes in queue q if(q.size()>0){ int front=q.front(); ans.push_back(arr[front]); }else{ ans.push_back(0); } //rest windows processing by sliding for(int i=k;i<n;i++){ if(i- q.front() >=k && !q.empty()){ // if the index present at front of q goes out of range from k q.pop(); //remove it } if(arr[i]<0){ q.push(i); } if(q.size()>0) ans.push_back(arr[q.front()]); else ans.push_back(0); } return ans; }