Minimize difference between the largest and smallest array elements by K replacements | C ++ program for above approach ; Function to find minimum difference between the largest and smallest element after K replacements ; Create a MaxHeap ; Create a MinHeap ; Update maxHeap and MinHeap with highest and smallest K elements respectively ; Insert current element into the MaxHeap ; If maxHeap size exceeds K + 1 ; Remove top element ; Insert current element into the MaxHeap ; If maxHeap size exceeds K + 1 ; Remove top element ; Store all max element from maxHeap ; Store all min element from minHeap ; Generating all K + 1 possibilities ; Return answer ; Driver Code ; Given array ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minDiff ( int A [ ] , int K , int N ) { if ( N <= K + 1 ) return 0 ; priority_queue < int , vector < int > , greater < int > > maxHeap ; priority_queue < int > minHeap ; for ( int i = 0 ; i < N ; i ++ ) { maxHeap . push ( A [ i ] ) ; if ( maxHeap . size ( ) > K + 1 ) maxHeap . pop ( ) ; minHeap . push ( A [ i ] ) ; if ( minHeap . size ( ) > K + 1 ) minHeap . pop ( ) ; } vector < int > maxList ; while ( maxHeap . size ( ) > 0 ) { maxList . push_back ( maxHeap . top ( ) ) ; maxHeap . pop ( ) ; } vector < int > minList ; while ( minHeap . size ( ) > 0 ) { minList . push_back ( minHeap . top ( ) ) ; minHeap . pop ( ) ; } int mindiff = INT_MAX ; for ( int i = 0 ; i <= K ; i ++ ) { mindiff = min ( mindiff , maxList [ i ] - minList [ K - i ] ) ; } return mindiff ; } int main ( ) { int A [ ] = { -1 , 3 , -1 , 8 , 5 , 4 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int K = 3 ; cout << minDiff ( A , K , N ) ; return 0 ; }