Minimize the maximum difference between adjacent elements in an array | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findKMin ( vector < int > arr , int n , int k ) { deque < int > Qi ( k ) ; int i ; for ( i = 0 ; i < k ; ++ i ) { while ( ( ! Qi . empty ( ) ) && arr [ i ] >= arr [ Qi . back ( ) ] ) Qi . push_back ( i ) ; } int minDiff = INT_MAX ; for ( ; i < n ; ++ i ) { minDiff = min ( minDiff , arr [ Qi . front ( ) ] ) ; while ( ( ! Qi . empty ( ) ) && Qi . front ( ) <= i - k ) Qi . pop_front ( ) ; while ( ( ! Qi . empty ( ) ) && arr [ i ] >= arr [ Qi . back ( ) ] ) Qi . pop_back ( ) ; Qi . push_back ( i ) ; } minDiff = min ( minDiff , arr [ Qi . front ( ) ] ) ; return minDiff ; } int minimumAdjacentDifference ( vector < int > a , int n , int k ) { vector < int > diff ( n - 1 ) ; for ( int i = 0 ; i < n - 1 ; i ++ ) { diff [ i ] = a [ i + 1 ] - a [ i ] ; } int answer = findKMin ( diff , n - 1 , n - k - 1 ) ; return answer ; } int main ( ) { int n = 5 ; int k = 2 ; vector < int > a = { 3 , 7 , 8 , 10 , 14 } ; cout << minimumAdjacentDifference ( a , n , k ) ; return 0 ; }