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 ; Given array arr [ ] ; Given subarray size ; Function call
def get_submaxarr ( arr , n , y ) : NEW_LINE INDENT j = 0 NEW_LINE stk = [ ] NEW_LINE maxarr = [ 0 ] * n NEW_LINE stk . append ( 0 ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT while ( len ( stk ) > 0 and arr [ i ] > arr [ stk [ - 1 ] ] ) : NEW_LINE INDENT maxarr [ stk [ - 1 ] ] = i - 1 NEW_LINE stk . pop ( ) NEW_LINE DEDENT stk . append ( i ) NEW_LINE DEDENT while ( stk ) : NEW_LINE INDENT maxarr [ stk [ - 1 ] ] = n - 1 NEW_LINE stk . pop ( ) NEW_LINE DEDENT submax = [ ] NEW_LINE for i in range ( n - y + 1 ) : NEW_LINE INDENT while ( maxarr [ j ] < i + y - 1 or j < i ) : NEW_LINE INDENT j += 1 NEW_LINE DEDENT submax . append ( arr [ j ] ) NEW_LINE DEDENT return submax NEW_LINE DEDENT def get_subminarr ( arr , n , y ) : NEW_LINE INDENT j = 0 NEW_LINE stk = [ ] NEW_LINE minarr = [ 0 ] * n NEW_LINE stk . append ( 0 ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT while ( stk and arr [ i ] < arr [ stk [ - 1 ] ] ) : NEW_LINE INDENT minarr [ stk [ - 1 ] ] = i NEW_LINE stk . pop ( ) NEW_LINE DEDENT stk . append ( i ) NEW_LINE DEDENT while ( stk ) : NEW_LINE INDENT minarr [ stk [ - 1 ] ] = n NEW_LINE stk . pop ( ) NEW_LINE DEDENT submin = [ ] NEW_LINE for i in range ( n - y + 1 ) : NEW_LINE INDENT while ( minarr [ j ] <= i + y - 1 or j < i ) : NEW_LINE INDENT j += 1 NEW_LINE DEDENT submin . append ( arr [ j ] ) NEW_LINE DEDENT return submin NEW_LINE DEDENT def getMinDifference ( Arr , N , Y ) : NEW_LINE INDENT submin = get_subminarr ( Arr , N , Y ) NEW_LINE submax = get_submaxarr ( Arr , N , Y ) NEW_LINE minn = submax [ 0 ] - submin [ 0 ] NEW_LINE b = len ( submax ) NEW_LINE for i in range ( 1 , b ) : NEW_LINE INDENT diff = submax [ i ] - submin [ i ] NEW_LINE minn = min ( minn , diff ) NEW_LINE DEDENT print ( minn ) NEW_LINE DEDENT arr = [ 1 , 2 , 3 , 3 , 2 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE Y = 4 NEW_LINE getMinDifference ( arr , N , Y ) NEW_LINE