Minimize difference between the largest and smallest array elements by K replacements | Python3 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 ; Given array ; Function call
import sys NEW_LINE def minDiff ( A , K ) : NEW_LINE INDENT if ( len ( A ) <= K + 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT maxHeap = [ ] NEW_LINE minHeap = [ ] NEW_LINE for n in A : NEW_LINE INDENT maxHeap . append ( n ) NEW_LINE maxHeap . sort ( ) NEW_LINE if ( len ( maxHeap ) > K + 1 ) : NEW_LINE INDENT del maxHeap [ 0 ] NEW_LINE DEDENT minHeap . append ( n ) NEW_LINE minHeap . sort ( ) NEW_LINE minHeap . reverse ( ) NEW_LINE if ( len ( minHeap ) > K + 1 ) : NEW_LINE INDENT del minHeap [ 0 ] NEW_LINE DEDENT DEDENT maxList = [ ] NEW_LINE while ( len ( maxHeap ) > 0 ) : NEW_LINE INDENT maxList . append ( maxHeap [ 0 ] ) NEW_LINE del maxHeap [ 0 ] NEW_LINE DEDENT minList = [ ] NEW_LINE while ( len ( minHeap ) > 0 ) : NEW_LINE INDENT minList . append ( minHeap [ 0 ] ) NEW_LINE del minHeap [ 0 ] NEW_LINE DEDENT mindiff = sys . maxsize NEW_LINE for i in range ( K ) : NEW_LINE INDENT mindiff = min ( mindiff , maxList [ i ] - minList [ K - i ] ) NEW_LINE DEDENT return mindiff NEW_LINE DEDENT A = [ - 1 , 3 , - 1 , 8 , 5 , 4 ] NEW_LINE K = 3 NEW_LINE print ( minDiff ( A , K ) ) NEW_LINE