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 ; Driver Code ; Given array arr [ ] ; Given subarray size ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > get_submaxarr ( int * arr , int n , int y ) { int j = 0 ; stack < int > stk ; vector < int > maxarr ( n ) ; stk . push ( 0 ) ; for ( int i = 1 ; i < n ; i ++ ) { while ( stk . empty ( ) == false and arr [ i ] > arr [ stk . top ( ) ] ) { maxarr [ stk . top ( ) ] = i - 1 ; stk . pop ( ) ; } stk . push ( i ) ; } while ( ! stk . empty ( ) ) { maxarr [ stk . top ( ) ] = n - 1 ; stk . pop ( ) ; } vector < int > submax ; for ( int i = 0 ; i <= n - y ; i ++ ) { while ( maxarr [ j ] < i + y - 1 or j < i ) { j ++ ; } submax . push_back ( arr [ j ] ) ; } return submax ; } vector < int > get_subminarr ( int * arr , int n , int y ) { int j = 0 ; stack < int > stk ; vector < int > minarr ( n ) ; stk . push ( 0 ) ; for ( int i = 1 ; i < n ; i ++ ) { while ( stk . empty ( ) == false and arr [ i ] < arr [ stk . top ( ) ] ) { minarr [ stk . top ( ) ] = i ; stk . pop ( ) ; } stk . push ( i ) ; } while ( ! stk . empty ( ) ) { minarr [ stk . top ( ) ] = n ; stk . pop ( ) ; } vector < int > submin ; for ( int i = 0 ; i <= n - y ; i ++ ) { while ( minarr [ j ] <= i + y - 1 or j < i ) { j ++ ; } submin . push_back ( arr [ j ] ) ; } return submin ; } void getMinDifference ( int Arr [ ] , int N , int Y ) { vector < int > submin = get_subminarr ( Arr , N , Y ) ; vector < int > submax = get_submaxarr ( Arr , N , Y ) ; int minn = submax [ 0 ] - submin [ 0 ] ; int b = submax . size ( ) ; for ( int i = 1 ; i < b ; i ++ ) { int dif = submax [ i ] - submin [ i ] ; minn = min ( minn , dif ) ; } cout << minn << " STRNEWLINE " ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 3 , 2 , 2 } ; int N = sizeof arr / sizeof arr [ 0 ] ; int Y = 4 ; getMinDifference ( arr , N , Y ) ; return 0 ; }