First negative integer in every window of size k | Java 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 Code
import java . util . * ; class GFG { static void printFirstNegativeInteger ( int arr [ ] , int n , int k ) { LinkedList < Integer > Di = new LinkedList < > ( ) ; int i ; for ( i = 0 ; i < k ; i ++ ) if ( arr [ i ] < 0 ) Di . add ( i ) ; for ( ; i < n ; i ++ ) { if ( ! Di . isEmpty ( ) ) System . out . print ( arr [ Di . peek ( ) ] + " ▁ " ) ; else System . out . print ( "0" + " ▁ " ) ; while ( ( ! Di . isEmpty ( ) ) && Di . peek ( ) < ( i - k + 1 ) ) Di . remove ( ) ; if ( arr [ i ] < 0 ) Di . add ( i ) ; } if ( ! Di . isEmpty ( ) ) System . out . print ( arr [ Di . peek ( ) ] + " ▁ " ) ; else System . out . print ( "0" + " ▁ " ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 12 , - 1 , - 7 , 8 , - 15 , 30 , 16 , 28 } ; int n = arr . length ; int k = 3 ; printFirstNegativeInteger ( arr , n , k ) ; } }