First negative integer in every window of size k | C ++ implementation to find the first negative integer in every window of size k ; function to find the first negative integer in every window of size k ; A Double Ended Queue , Di that will store indexes of useful array elements for the current window of size k . The useful elements are all negative integers . ; Process first k ( or first window ) elements of array ; Add current element at the rear of Di if it is a negative integer ; Process rest of the elements , i . e . , from arr [ k ] to arr [ n - 1 ] ; if Di is not empty then the element at the front of the queue is the first negative integer of the previous window ; else the window does not have a negative integer ; Remove the elements which are out of this window ; Remove from front of queue ; Add current element at the rear of Di if it is a negative integer ; Print the first negative integer of last window ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printFirstNegativeInteger ( int arr [ ] , int n , int k ) { deque < int > Di ; int i ; for ( i = 0 ; i < k ; i ++ ) if ( arr [ i ] < 0 ) Di . push_back ( i ) ; for ( ; i < n ; i ++ ) { if ( ! Di . empty ( ) ) cout << arr [ Di . front ( ) ] << " ▁ " ; else cout << "0" << " ▁ " ; while ( ( ! Di . empty ( ) ) && Di . front ( ) < ( i - k + 1 ) ) Di . pop_front ( ) ; if ( arr [ i ] < 0 ) Di . push_back ( i ) ; } if ( ! Di . empty ( ) ) cout << arr [ Di . front ( ) ] << " ▁ " ; else cout << "0" << " ▁ " ; } int main ( ) { int arr [ ] = { 12 , -1 , -7 , 8 , -15 , 30 , 16 , 28 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 3 ; printFirstNegativeInteger ( arr , n , k ) ; return 0 ; }