Minimize the maximum difference between adjacent elements in an array | Python3 implementation to find the minimum of the maximum difference of the adjacent elements after removing K elements from the array ; Function to find the minimum different in the subarrays of size K in the array ; Create a Double Ended Queue , Qi that will store indexes of array elements , queue will store indexes of useful elements in every window ; Process first k ( or first window ) elements of array ; For every element , the previous smaller elements are useless so remove them from Qi ; Add new element at rear of queue ; Process rest of the elements , i . e . , from arr [ k ] to arr [ n - 1 ] ; The element at the front of the queue is the largest element of previous window ; Remove the elements which are out of this window ; Remove all elements smaller than the currently being added element ( remove useless elements ) ; Add current element at the rear of Qi ; Compare the maximum element of last window ; Function to find the minimum of the maximum difference of the adjacent elements after removing K elements from the array ; Create the difference array ; Find minimum of all maximum of subarray sizes n - k - 1 ; Driver code
import sys NEW_LINE def findKMin ( arr , n , k ) : NEW_LINE INDENT Qi = [ ] NEW_LINE i = 0 NEW_LINE for j in range ( k ) : NEW_LINE INDENT while ( ( len ( Qi ) != 0 ) and arr [ i ] >= arr [ Qi [ - 1 ] ] ) : NEW_LINE Qi . append ( i ) NEW_LINE i += 1 NEW_LINE DEDENT minDiff = sys . maxsize ; NEW_LINE for j in range ( i , n ) : NEW_LINE INDENT minDiff = min ( minDiff , arr [ Qi [ 0 ] ] ) NEW_LINE while ( ( len ( Qi ) != 0 ) and Qi [ 0 ] <= i - k ) : NEW_LINE INDENT Qi . pop ( 0 ) NEW_LINE DEDENT while ( ( len ( Qi ) != 0 ) and arr [ i ] >= arr [ Qi [ - 1 ] ] ) : NEW_LINE INDENT Qi . pop ( ) NEW_LINE DEDENT Qi . append ( i ) NEW_LINE i += 1 NEW_LINE DEDENT minDiff = min ( minDiff , arr [ Qi [ 0 ] ] ) NEW_LINE return minDiff NEW_LINE DEDENT def minimumAdjacentDifference ( a , n , k ) : NEW_LINE INDENT diff = [ 0 for i in range ( n - 1 ) ] NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT diff [ i ] = a [ i + 1 ] - a [ i ] NEW_LINE DEDENT answer = findKMin ( diff , n - 1 , n - k - 1 ) NEW_LINE return answer NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE k = 2 NEW_LINE a = [ 3 , 7 , 8 , 10 , 14 ] NEW_LINE print ( minimumAdjacentDifference ( a , n , k ) ) NEW_LINE DEDENT