Given an array A[] consisting of N integers, the task is to find the minimum difference between the largest and the smallest element in the given array after replacing K elements.
Examples:
Input: A[] = {-1, 3, -1, 8, 5, 4}, K = 3
Output: 2
Explanation:Replace A[0] and A[2] by 3 and 4 respectively. Replace A[3] by 5. Modified array A[] is {3, 3, 4, 5, 5, 4}. Therefore, required output = (5-3) = 2.Input: A[] = {10, 10, 3, 4, 10}, K = 2
Output: 0
Sorting Approach: The idea is to sort the given array.
- Check for all K + 1 possibilities of
- removing X ( 0 ? X ? K ) elements from the start of the array, and
- removing K – X elements from the end of the array
- Then calculate the minimum difference possible.
- Finally, print the minimum difference obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum difference// between largest and smallest element// after K replacementsint minDiff(int A[], int K, int n){ // Sort array in ascending order sort(A, A + n); if (n <= K) return 0; // Minimum difference int mindiff = A[n - 1] - A[0]; if (K == 0) return mindiff; // Check for all K + 1 possibilities for (int i = 0, j = n - 1 - K; j < n;) { mindiff = min(mindiff, A[j] - A[i]); i++; j++; } // Return answer return mindiff;}// Driver Codeint main(){ // Given array int A[] = { -1, 3, -1, 8, 5, 4 }; int K = 3; // Length of array int n = sizeof(A) / sizeof(A[0]); // Prints the minimum possible difference cout << minDiff(A, K, n); return 0;}// This code is contributed by 29AjayKumar |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find minimum difference // between largest and smallest element // after K replacements static int minDiff(int[] A, int K) { // Sort array in ascending order Arrays.sort(A); // Length of array int n = A.length; if (n <= K) return 0; // Minimum difference int mindiff = A[n - 1] - A[0]; if (K == 0) return mindiff; // Check for all K + 1 possibilities for (int i = 0, j = n - 1 - K; j < n;) { mindiff = Math.min(mindiff, A[j] - A[i]); i++; j++; } // Return answer return mindiff; } // Driver Code public static void main(String[] args) { // Given array int A[] = { -1, 3, -1, 8, 5, 4 }; int K = 3; // Prints the minimum possible difference System.out.println(minDiff(A, K)); }} |
Python3
# Python3 program for the above approach# Function to find minimum difference# between largest and smallest element# after K replacementsdef minDiff(A, K): # Sort array in ascending order A.sort() # Length of array n = len(A) if (n <= K): return 0 # Minimum difference mindiff = A[n - 1] - A[0] if (K == 0): return mindiff # Check for all K + 1 possibilities i = 0 for j in range(n - 1 - K, n): mindiff = min(mindiff, A[j] - A[i]) i += 1 j += 1 # Return answer return mindiff# Driver Codeif __name__ == '__main__': # Given array A = [-1, 3, -1, 8, 5, 4] K = 3 # Prints the minimum possible difference print(minDiff(A, K)) # This code is contributed by 29AjayKumar |
C#
// C# program for the above approachusing System;class GFG { // Function to find minimum difference // between largest and smallest element // after K replacements static int minDiff(int[] A, int K) { // Sort array in ascending order Array.Sort(A); // Length of array int n = A.Length; if (n <= K) return 0; // Minimum difference int mindiff = A[n - 1] - A[0]; if (K == 0) return mindiff; // Check for all K + 1 possibilities for (int i = 0, j = n - 1 - K; j < n;) { mindiff = Math.Min(mindiff, A[j] - A[i]); i++; j++; } // Return answer return mindiff; } // Driver Code public static void Main(String[] args) { // Given array int[] A = { -1, 3, -1, 8, 5, 4 }; int K = 3; // Prints the minimum possible difference Console.WriteLine(minDiff(A, K)); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program for the above approach // Function to find minimum difference // between largest and smallest element // after K replacements function minDiff(A, K) { // Sort array in ascending order A.sort(function(a, b){return a - b}); // Length of array let n = A.length; if (n <= K) return 0; // Minimum difference let mindiff = A[n - 1] - A[0]; if (K == 0) return mindiff; // Check for all K + 1 possibilities for(let i = 0, j = n - 1 - K; j < n;) { mindiff = Math.min(mindiff, A[j] - A[i]); i++; j++; } // Return answer return mindiff; } // Given array let A = [ -1, 3, -1, 8, 5, 4 ]; let K = 3; // Prints the minimum possible difference document.write(minDiff(A, K)); // This code is contributed by mukesh07.</script> |
Output
2
Time Complexity: O(NlogN)
Auxiliary Space: O(1)
Heap-based Approach: This approach is similar to the above approach, but we will find the K minimum and K maximum array elements using Min Heap and Max Heap respectively.
Follow the steps below to solve the problem:
- Initialize two PriorityQueues, min-heap and max-heap.
- Traverse the given array and add all elements one by one into the Heaps. If the size of the Heap exceeds K, in any of the heaps, remove the element present at the top of that Queue.
- Store the K maximum and the minimum elements in two separate arrays, maxList and minList, and initialize a variable, say minDiff to store the minimum difference.
- Iterate over the arrays and for every index, say i, update minDiff as minDiff = min(minDiff, maxList[i]-minList[ K – i ]) and print final value of minDiff as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum difference// between the largest and smallest// element after K replacementsint minDiff(int A[], int K, int N){ if (N <= K + 1) return 0; // Create a MaxHeap priority_queue<int, vector<int>, greater<int> > maxHeap; // Create a MinHeap priority_queue<int> minHeap; // Update maxHeap and MinHeap with highest // and smallest K elements respectively for (int i = 0; i < N; i++) { // Insert current element // into the MaxHeap maxHeap.push(A[i]); // If maxHeap size exceeds K + 1 if (maxHeap.size() > K + 1) // Remove top element maxHeap.pop(); // Insert current element // into the MaxHeap minHeap.push(A[i]); // If maxHeap size exceeds K + 1 if (minHeap.size() > K + 1) // Remove top element minHeap.pop(); } // Store all max element from maxHeap vector<int> maxList; while (maxHeap.size() > 0) { maxList.push_back(maxHeap.top()); maxHeap.pop(); } // Store all min element from minHeap vector<int> minList; while (minHeap.size() > 0) { minList.push_back(minHeap.top()); minHeap.pop(); } int mindiff = INT_MAX; // Generating all K + 1 possibilities for (int i = 0; i <= K; i++) { mindiff = min(mindiff, maxList[i] - minList[K - i]); } // Return answer return mindiff;}// Driver Codeint main(){ // Given array int A[] = { -1, 3, -1, 8, 5, 4 }; int N = sizeof(A) / sizeof(A[0]); int K = 3; // Function call cout << minDiff(A, K, N); return 0;}// This code is contributed by Dharanendra L V |
Java
// Java program for above approachimport java.lang.*;import java.util.*;class GFG { // Function to find minimum difference // between the largest and smallest // element after K replacements static int minDiff(int[] A, int K) { if (A.length <= K + 1) return 0; // Create a MaxHeap PriorityQueue<Integer> maxHeap = new PriorityQueue<>(); // Create a MinHeap PriorityQueue<Integer> minHeap = new PriorityQueue<>( Collections.reverseOrder()); // Update maxHeap and MinHeap with highest // and smallest K elements respectively for (int n : A) { // Insert current element // into the MaxHeap maxHeap.add(n); // If maxHeap size exceeds K + 1 if (maxHeap.size() > K + 1) // Remove top element maxHeap.poll(); // Insert current element // into the MaxHeap minHeap.add(n); // If maxHeap size exceeds K + 1 if (minHeap.size() > K + 1) // Remove top element minHeap.poll(); } // Store all max element from maxHeap List<Integer> maxList = new ArrayList<>(); while (maxHeap.size() > 0) maxList.add(maxHeap.poll()); // Store all min element from minHeap List<Integer> minList = new ArrayList<>(); while (minHeap.size() > 0) minList.add(minHeap.poll()); int mindiff = Integer.MAX_VALUE; // Generating all K + 1 possibilities for (int i = 0; i <= K; i++) { mindiff = Math.min(mindiff, maxList.get(i) - minList.get(K - i)); } // Return answer return mindiff; } // Driver Code public static void main(String[] args) { // Given array int A[] = { -1, 3, -1, 8, 5, 4 }; int K = 3; // Function call System.out.println(minDiff(A, K)); }} |
Python3
# Python3 program for above approachimport sysimport heapq# Function to find minimum difference# between the largest and smallest# element after K replacementsdef minDiff(A, K): if (len(A) <= K + 1): return 0 # Create a MaxHeap maxHeap = [] heapq.heapify(maxHeap) # Create a MinHeap minHeap = [] heapq.heapify(minHeap) # Update maxHeap and MinHeap with highest # and smallest K elements respectively for n in A: # Insert current element # into the MaxHeap heapq.heappush(maxHeap, n) # If maxHeap size exceeds K + 1 if (len(maxHeap) > K + 1): # Remove top element heapq.heappop(maxHeap) # Insert current element # into the MaxHeap heapq.heappush(minHeap, -n) # If maxHeap size exceeds K + 1 if (len(minHeap) > K + 1): # Remove top element heapq.heappop(minHeap) # Store all max element from maxHeap maxList = [] while (len(maxHeap) > 0): maxList.append(heapq.heappop(maxHeap)) # Store all min element from minHeap minList = [] while (len(minHeap) > 0): minList.append(-1 * heapq.heappop(minHeap)) mindiff = sys.maxsize # Generating all K + 1 possibilities for i in range(K): mindiff = min(mindiff, maxList[i] - minList[K - i]) # Return answer return mindiff# Drive Codeif __name__ == "__main__": # Given array A = [-1, 3, -1, 8, 5, 4] K = 3 # Function call print(minDiff(A, K)) # This code is contributed by divyesh072019. |
C#
// C# program for above approachusing System;using System.Collections.Generic;class GFG { // Function to find minimum difference // between the largest and smallest // element after K replacements static int minDiff(int[] A, int K) { if (A.Length <= K + 1) return 0; // Create a MaxHeap List<int> maxHeap = new List<int>(); // Create a MinHeap List<int> minHeap = new List<int>(); // Update maxHeap and MinHeap with highest // and smallest K elements respectively foreach(int n in A) { // Insert current element // into the MaxHeap maxHeap.Add(n); maxHeap.Sort(); // If maxHeap size exceeds K + 1 if (maxHeap.Count > K + 1) // Remove top element maxHeap.RemoveAt(0); // Insert current element // into the MaxHeap minHeap.Add(n); minHeap.Sort(); minHeap.Reverse(); // If maxHeap size exceeds K + 1 if (minHeap.Count > K + 1) // Remove top element minHeap.RemoveAt(0); } // Store all max element from maxHeap List<int> maxList = new List<int>(); while (maxHeap.Count > 0) { maxList.Add(maxHeap[0]); maxHeap.RemoveAt(0); } // Store all min element from minHeap List<int> minList = new List<int>(); while (minHeap.Count > 0) { minList.Add(minHeap[0]); minHeap.RemoveAt(0); } int mindiff = Int32.MaxValue; // Generating all K + 1 possibilities for (int i = 0; i < K; i++) { mindiff = Math.Min(mindiff, maxList[i] - minList[K - i]); } // Return answer return mindiff; } // Driver code static void Main() { // Given array int[] A = { -1, 3, -1, 8, 5, 4 }; int K = 3; // Function call Console.WriteLine(minDiff(A, K)); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript program for above approach// Function to find minimum difference// between the largest and smallest// element after K replacementsfunction minDiff(A, K, N){ if (N <= K + 1) return 0; // Create a MaxHeap var maxHeap = []; // Create a MinHeap var minHeap = []; // Update maxHeap and MinHeap with highest // and smallest K elements respectively for (var i = 0; i < N; i++) { // Insert current element // into the MaxHeap maxHeap.push(A[i]); maxHeap.sort((a,b)=>b-a); // If maxHeap size exceeds K + 1 if (maxHeap.length > K + 1) // Remove top element maxHeap.pop(); // Insert current element // into the MaxHeap minHeap.push(A[i]); minHeap.sort((a,b)=>a-b); // If maxHeap size exceeds K + 1 if (minHeap.length > K + 1) // Remove top element minHeap.pop(); } // Store all max element from maxHeap var maxList = []; while (maxHeap.length > 0) { maxList.push(maxHeap[maxHeap.length-1]); maxHeap.pop(); } // Store all min element from minHeap var minList = []; while (minHeap.length > 0) { minList.push(minHeap[minHeap.length-1]); minHeap.pop(); } var mindiff = 1000000000; // Generating all K + 1 possibilities for (var i = 0; i <= K; i++) { mindiff = Math.min(mindiff, maxList[i] - minList[K - i]); } // Return answer return mindiff;}// Driver Code// Given arrayvar A = [-1, 3, -1, 8, 5, 4];var N = A.length;var K = 3;// Function calldocument.write(minDiff(A, K, N));// This code is contributed by noob2000.</script> |
Output
2
Time Complexity: O(N*log N) where N is the size of the given array.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
