Untitled

mail@pastecode.io avatarunknown
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;
}