Minimize difference between the largest and smallest array elements by K replacements | Java 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
import java . util . * ; import java . lang . * ; class GFG { static int minDiff ( int [ ] A , int K ) { if ( A . length <= K + 1 ) return 0 ; PriorityQueue < Integer > maxHeap = new PriorityQueue < > ( ) ; PriorityQueue < Integer > minHeap = new PriorityQueue < > ( Collections . reverseOrder ( ) ) ; for ( int n : A ) { maxHeap . add ( n ) ; if ( maxHeap . size ( ) > K + 1 ) maxHeap . poll ( ) ; minHeap . add ( n ) ; if ( minHeap . size ( ) > K + 1 ) minHeap . poll ( ) ; } List < Integer > maxList = new ArrayList < > ( ) ; while ( maxHeap . size ( ) > 0 ) maxList . add ( maxHeap . poll ( ) ) ; List < Integer > minList = new ArrayList < > ( ) ; while ( minHeap . size ( ) > 0 ) minList . add ( minHeap . poll ( ) ) ; int mindiff = Integer . MAX_VALUE ; for ( int i = 0 ; i <= K ; i ++ ) { mindiff = Math . min ( mindiff , maxList . get ( i ) - minList . get ( K - i ) ) ; } return mindiff ; } public static void main ( String [ ] args ) { int A [ ] = { - 1 , 3 , - 1 , 8 , 5 , 4 } ; int K = 3 ; System . out . println ( minDiff ( A , K ) ) ; } }