Min difference between maximum and minimum element in all Y size subarrays | C # program for the above approach ; 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 ; Given array arr [ ] ; Given subarray size ; Function Call
using System ; using System . Collections . Generic ; class GFG { static List < int > get_submaxarr ( int [ ] arr , int n , int y ) { int j = 0 ; Stack < int > stk = new Stack < int > ( ) ; int [ ] maxarr = new int [ n ] ; Array . Fill ( maxarr , 0 ) ; stk . Push ( 0 ) ; for ( int i = 1 ; i < n ; i ++ ) { while ( stk . Count != 0 && arr [ i ] > arr [ stk . Peek ( ) ] ) { maxarr [ stk . Peek ( ) ] = i - 1 ; stk . Pop ( ) ; } stk . Push ( i ) ; } while ( stk . Count != 0 ) { maxarr [ stk . Count ] = n - 1 ; stk . Pop ( ) ; } List < int > submax = new List < int > ( ) ; for ( int i = 0 ; i <= n - y ; i ++ ) { while ( maxarr [ j ] < i + y - 1 j < i ) { j ++ ; } submax . Add ( arr [ j ] ) ; } return submax ; } static List < int > get_subminarr ( int [ ] arr , int n , int y ) { int j = 0 ; Stack < int > stk = new Stack < int > ( ) ; int [ ] minarr = new int [ n ] ; Array . Fill ( minarr , 0 ) ; stk . Push ( 0 ) ; for ( int i = 1 ; i < n ; i ++ ) { while ( stk . Count != 0 && arr [ i ] < arr [ stk . Peek ( ) ] ) { minarr [ stk . Peek ( ) ] = i ; stk . Pop ( ) ; } stk . Push ( i ) ; } while ( stk . Count != 0 ) { minarr [ stk . Peek ( ) ] = n ; stk . Pop ( ) ; } List < int > submin = new List < int > ( ) ; for ( int i = 0 ; i <= n - y ; i ++ ) { while ( minarr [ j ] <= i + y - 1 j < i ) { j ++ ; } submin . Add ( arr [ j ] ) ; } return submin ; } static void getMinDifference ( int [ ] Arr , int N , int Y ) { List < int > submin = get_subminarr ( Arr , N , Y ) ; List < int > submax = get_submaxarr ( Arr , N , Y ) ; int minn = submax [ 0 ] - submin [ 0 ] ; int b = submax . Count ; for ( int i = 1 ; i < b ; i ++ ) { int dif = submax [ i ] - submin [ i ] + 1 ; minn = Math . Min ( minn , dif ) ; } Console . WriteLine ( minn ) ; } static void Main ( ) { int [ ] arr = { 1 , 2 , 3 , 3 , 2 , 2 } ; int N = arr . Length ; int Y = 4 ; getMinDifference ( arr , N , Y ) ; } }