Minimize difference between maximum and minimum array elements by exactly K removals
Given an array arr[] consisting of N positive integers and an integer K, the task is to minimize the difference between the maximum and minimum element in the given array after removing exactly K elements.
Examples:
Input: arr[] = {5, 1, 6, 7, 12, 10}, K = 3
Output: 2
Explanation:
Remove elements 12, 10 and 1 from the given array.
The array modifies to {5, 6, 7}.
The difference between the minimum and maximum element is 7 – 5 = 2.Input: arr[] = {14, 5, 61, 10, 21, 12, 54}, K = 4
Output: 4
Explanation:
Remove elements 61, 54, 5 and 21 from the given array.
The array modifies to {14, 10, 12}.
The difference between the minimum and maximum element is 14 – 10 = 4.
Approach: The idea to solve the given problem is that the difference will be minimized by removing either the minimum element in an array or the maximum element in the array. Follow the steps below to solve the problem:
- Sort the array arr[] in ascending order.
- Initialize variables left = 0 and right = (N – 1).
- Iterate for K times and change the maximum or minimum to 0 according to the following condition:
- If arr[right – 1] – arr[left] < arr[right] – arr[left + 1], then change arr[right] to 0 and decrement right pointer by 1.
- Else, change arr[left] as 0 and increment the left pointer by 1.
- After the above steps, the difference between the elements at the left and right index is the required minimum difference.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to minimize the difference // of the maximum and minimum array // elements by removing K elements void minimumRange( int arr[], int N, int K) { // Base Condition if (K >= N) { cout << 0; return ; } // Sort the array sort(arr, arr + N); // Initialize left and right pointers int left = 0, right = N - 1, i; // Iterate for K times for (i = 0; i < K; i++) { // Removing right element // to reduce the difference if (arr[right - 1] - arr[left] < arr[right] - arr[left + 1]) right--; // Removing the left element // to reduce the difference else left++; } // Print the minimum difference cout << arr[right] - arr[left]; } // Driver Code int main() { int arr[] = { 5, 10, 12, 14, 21, 54, 61 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 4; // Function Call minimumRange(arr, N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to minimize the difference // of the maximum and minimum array // elements by removing K elements static void minimumRange( int arr[], int N, int K) { // Base Condition if (K >= N) { System.out.print( 0 ); return ; } // Sort the array Arrays.sort(arr); // Initialize left and right pointers int left = 0 , right = N - 1 , i; // Iterate for K times for (i = 0 ; i < K; i++) { // Removing right element // to reduce the difference if (arr[right - 1 ] - arr[left] < arr[right] - arr[left + 1 ]) right--; // Removing the left element // to reduce the difference else left++; } // Print the minimum difference System.out.print(arr[right] - arr[left]); } // Driver Code public static void main(String[] args) { int arr[] = { 5 , 10 , 12 , 14 , 21 , 54 , 61 }; int N = arr.length; int K = 4 ; // Function Call minimumRange(arr, N, K); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach # Function to minimize the difference # of the maximum and minimum array # elements by removing K elements def minimumRange(arr, N, K) : # Base Condition if (K > = N) : print ( 0 , end = ''); return ; # Sort the array arr.sort(); # Initialize left and right pointers left = 0 ; right = N - 1 ; # Iterate for K times for i in range (K) : # Removing right element # to reduce the difference if (arr[right - 1 ] - arr[left] < arr[right] - arr[left + 1 ]) : right - = 1 ; # Removing the left element # to reduce the difference else : left + = 1 ; # Print the minimum difference print (arr[right] - arr[left], end = ''); # Driver Code if __name__ = = "__main__" : arr = [ 5 , 10 , 12 , 14 , 21 , 54 , 61 ]; N = len (arr); K = 4 ; # Function Call minimumRange(arr, N, K); # This code is contributed by AnkitRai01 |
C#
// C# program for the above approach using System; class GFG{ // Function to minimize the difference // of the maximum and minimum array // elements by removing K elements static void minimumRange( int []arr, int N, int K) { // Base Condition if (K >= N) { Console.Write(0); return ; } // Sort the array Array.Sort(arr); // Initialize left and right pointers int left = 0, right = N - 1, i; // Iterate for K times for (i = 0; i < K; i++) { // Removing right element // to reduce the difference if (arr[right - 1] - arr[left] < arr[right] - arr[left + 1]) right--; // Removing the left element // to reduce the difference else left++; } // Print the minimum difference Console.Write(arr[right] - arr[left]); } // Driver Code public static void Main(String[] args) { int []arr = { 5, 10, 12, 14, 21, 54, 61 }; int N = arr.Length; int K = 4; // Function Call minimumRange(arr, N, K); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function to minimize the difference // of the maximum and minimum array // elements by removing K elements function minimumRange(arr, N, K) { // Base Condition if (K >= N) { document.write( 0); return ; } // Sort the array arr.sort((a,b)=> a-b); // Initialize left and right pointers var left = 0, right = N - 1, i; // Iterate for K times for (i = 0; i < K; i++) { // Removing right element // to reduce the difference if (arr[right - 1] - arr[left] < arr[right] - arr[left + 1]) right--; // Removing the left element // to reduce the difference else left++; } // Print the minimum difference document.write( arr[right] - arr[left]); } // Driver Code var arr = [5, 10, 12, 14, 21, 54, 61]; var N = arr.length; var K = 4; // Function Call minimumRange(arr, N, K); </script> |
4
Time Complexity: O(N*log N)
Auxiliary Space: O(1)