Min difference between maximum and minimum element in all Y size subarrays | Function to get the maximum of all the subarrays of size Y ; ith index of maxarr array will be the index upto which Arr [ i ] is maximum ; Stack is used to find the next larger element and keeps track of index of current iteration ; Loop for remaining indexes ; j < i used to keep track whether jth element is inside or outside the window ; Return submax ; Function to get the minimum for all subarrays of size Y ; ith index of minarr array will be the index upto which Arr [ i ] is minimum ; Stack is used to find the next smaller element and keeping track of index of current iteration ; Loop for remaining indexes ; j < i used to keep track whether jth element is inside or outside the window ; Return submin ; Function to get minimum difference ; Create submin and submax arrays ; Store initial difference ; Calculate temporary difference ; Final minimum difference ; Driver Code Given array arr [ ] ; Given array arr [ ] ; Given subarray size ; Function Call
function get_submaxarr ( arr , n , y ) { var j = 0 ; var stk = [ ] ; var maxarr = Array ( n ) ; stk . push ( 0 ) ; for ( var i = 1 ; i < n ; i ++ ) { while ( stk . length != 0 && arr [ i ] > arr [ stk [ stk . length - 1 ] ] ) { maxarr [ stk [ stk . length - 1 ] ] = i - 1 ; stk . pop ( ) ; } stk . push ( i ) ; } while ( stk . length != 0 ) { maxarr [ stk [ stk . length - 1 ] ] = n - 1 ; stk . pop ( ) ; } var submax = [ ] ; for ( var i = 0 ; i <= n - y ; i ++ ) { while ( maxarr [ j ] < i + y - 1 j < i ) { j ++ ; } submax . push ( arr [ j ] ) ; } return submax ; } function get_subminarr ( arr , n , y ) { var j = 0 ; var stk = [ ] ; var minarr = Array ( n ) ; stk . push ( 0 ) ; for ( var i = 1 ; i < n ; i ++ ) { while ( stk . length != 0 && arr [ i ] < arr [ stk [ stk . length - 1 ] ] ) { minarr [ stk [ stk . length - 1 ] ] = i ; stk . pop ( ) ; } stk . push ( i ) ; } while ( stk . length != 0 ) { minarr [ stk [ stk . length - 1 ] ] = n ; stk . pop ( ) ; } var submin = [ ] ; for ( var i = 0 ; i <= n - y ; i ++ ) { while ( minarr [ j ] <= i + y - 1 j < i ) { j ++ ; } submin . push ( arr [ j ] ) ; } return submin ; } function getMinDifference ( Arr , N , Y ) { var submin = get_subminarr ( Arr , N , Y ) ; var submax = get_submaxarr ( Arr , N , Y ) ; var minn = submax [ 0 ] - submin [ 0 ] ; var b = submax . length ; for ( var i = 1 ; i < b ; i ++ ) { var dif = submax [ i ] - submin [ i ] ; minn = Math . min ( minn , dif ) ; } document . write ( minn + " " ) ; } var arr = [ 1 , 2 , 3 , 3 , 2 , 2 ] ; var N = arr . length var arr = [ 1 , 2 , 3 , 3 , 2 , 2 ] ; var N = arr . length var Y = 4 ; getMinDifference ( arr , N , Y ) ;