Given an array arr[] consisting of N integers(N > 2), the task is to minimize the maximum difference between any pair of elements (arr[i], arr[j]) by removing exactly one element.
Examples:
Input: arr[] = {1, 3, 4, 7}
Output: 3
Explanation:
Removing the element 7 from array, modifies the array to {1, 3, 4}.
Here (4, 1) has difference = 4 – 1 = 3 which is minimum possible maximum difference.Input: arr[] = {1, 2, 3, 4}
Output: 2
Naive Approach: The simplest approach to solve the given problem is to remove every element one by one and check which element gives the minimized maximum difference between every pair of elements.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach: The above approach can also be optimized by observing the fact that the maximum difference is equal to the difference between the maximum and the minimum element of the given array. So, removing the maximum element or removing the minimum element always gives the optimal answer.
Therefore, the idea is to sort the given array in ascending order and print the minimum of the value (arr[N – 2] – arr[0]) and (arr[N – 1] – arr[1]) as the resultant minimized maximum difference.
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 the minimum maximum // difference after removing one element int findMinDifference( int arr[], int n) { // Stores the resultant minimized // maximum difference int ans = 0; // Sort the given array sort(arr, arr + n); // Find the minimum maximum // difference ans = min(arr[n - 2] - arr[0], arr[n - 1] - arr[1]); // Return the result return ans; } // Driver Code int main() { int arr[] = { 1, 3, 4, 7 }; int N = sizeof (arr) / sizeof (arr[0]); cout << findMinDifference(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to find the minimum maximum // difference after removing one element static int findMinDifference( int []arr, int n) { // Stores the resultant minimized // maximum difference int ans = 0 ; // Sort the given array Arrays.sort(arr); // Find the minimum maximum // difference ans = Math.min(arr[n - 2 ] - arr[ 0 ], arr[n - 1 ] - arr[ 1 ]); // Return the result return ans; } // Driver Code public static void main (String[] args) { int []arr = { 1 , 3 , 4 , 7 }; int N = arr.length; System.out.println(findMinDifference(arr, N)); } } // This code is contributed by unknown2108 |
Python3
# Python3 program for the above approach # Function to find the minimum maximum # difference after removing one element def findMinDifference(arr, n): # Stores the resultant minimized # maximum difference ans = 0 # Sort the given array arr = sorted (arr) # Find the minimum maximum # difference ans = min (arr[n - 2 ] - arr[ 0 ], arr[n - 1 ] - arr[ 1 ]) # Return the result return ans # Driver Code if __name__ = = '__main__' : arr = [ 1 , 3 , 4 , 7 ] N = len (arr) print (findMinDifference(arr, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the minimum maximum // difference after removing one element static int findMinDifference( int []arr, int n) { // Stores the resultant minimized // maximum difference int ans = 0; // Sort the given array Array.Sort(arr); // Find the minimum maximum // difference ans = Math.Min(arr[n - 2] - arr[0], arr[n - 1] - arr[1]); // Return the result return ans; } // Driver Code public static void Main() { int []arr = { 1, 3, 4, 7 }; int N = arr.Length; Console.Write(findMinDifference(arr, N)); } } // This code is contributed by ipg2016107 |
Javascript
<script> // Javascript program for the above approach // Function to find the minimum maximum // difference after removing one element function findMinDifference(arr, n) { // Stores the resultant minimized // maximum difference let ans = 0; // Sort the given array arr.sort( function (a,b){ return a-b;}); // Find the minimum maximum // difference ans = Math.min(arr[n - 2] - arr[0], arr[n - 1] - arr[1]); // Return the result return ans; } // Driver Code let arr=[1, 3, 4, 7]; let N = arr.length; document.write(findMinDifference(arr, N)); // This code is contributed by patel2127 </script> |
3
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Efficient Approach:-
- As in the above approach we are either removing the maximum element or the minimum element
- So we can do this work without sorting
- We have to just find out the 2 maximum and 2 minimum elements from the array
- Answer will be minimum of (2nd largest-first minimum) or (first lasgest-second minimum).
Implementation:-
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum maximum // difference after removing one element int findMinDifference( int arr[], int n) { //taking variables to store 2 max and 2 min elements int firstmin=INT_MAX,secondmin=INT_MAX,firstmax=INT_MIN,secondmax=INT_MIN; //iterating over array for ( int i=0;i<n;i++) { //if found min element than firstmin if (arr[i]<firstmin) { //updating secondmin secondmin=firstmin; //updating firstmin firstmin=arr[i]; } //if found element small than secondmin else if (arr[i]<secondmin) { secondmin=arr[i]; } //if found element larger than firstmax if (arr[i]>firstmax) { //updating second max secondmax=firstmax; //updating first max firstmax=arr[i]; } //if found element greater than second max else if (arr[i]>secondmax) { secondmax=arr[i]; } } //returning answer return min(secondmax-firstmin,firstmax-secondmin); } // Driver Code int main() { int arr[] = { 1, 3, 4, 7 }; int N = sizeof (arr) / sizeof (arr[0]); cout << findMinDifference(arr, N); return 0; } //This code is contributed by shubhamrajput6156 |
Java
// Java program for the above approach import java.lang.*; import java.util.*; class Main { // Function to find the minimum maximum // difference after removing one element static int findMinDifference( int arr[], int n) { // taking variables to store 2 max and 2 min // elements int firstmin = Integer.MAX_VALUE, secondmin = Integer.MAX_VALUE, firstmax = Integer.MIN_VALUE, secondmax = Integer.MIN_VALUE; // iterating over array for ( int i = 0 ; i < n; i++) { // if found min element than firstmin if (arr[i] < firstmin) { // updating secondmin secondmin = firstmin; // updating firstmin firstmin = arr[i]; } // if found element small than secondmin else if (arr[i] < secondmin) { secondmin = arr[i]; } // if found element larger than firstmax if (arr[i] > firstmax) { // updating second max secondmax = firstmax; // updating first max firstmax = arr[i]; } // if found element greater than second max else if (arr[i] > secondmax) { secondmax = arr[i]; } } // returning answer return Math.min(secondmax - firstmin, firstmax - secondmin); } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 3 , 4 , 7 }; int N = arr.length; System.out.println(findMinDifference(arr, N)); } } |
Python3
# Python program for the above approach import sys # Function to find the minimum maximum # difference after removing one element def findMinDifference(arr, n): # taking variables to store 2 max and 2 min elements firstmin = sys.maxsize secondmin = sys.maxsize firstmax = - sys.maxsize - 1 secondmax = - sys.maxsize - 1 for i in range (n): # if found min element than firstmin if arr[i] < firstmin: # updating secondmin secondmin = firstmin #updating firstmin firstmin = arr[i] # if found element small than secondmin elif arr[i] < secondmin: secondmin = arr[i] # if found element larger than firstmax if arr[i] > firstmax: # update second max secondmax = firstmax # update first max firstmax = arr[i] # if found element greater than second max elif arr[i] > secondmax: secondmax = arr[i] # returning answer return min (secondmax - firstmin, firstmax - secondmin) # driver code arr = [ 1 , 3 , 4 , 7 ] N = len (arr) print (findMinDifference(arr, N)) # This code is contributed by redmoonz. |
Javascript
// Java program for the above approach // Function to find the minimum maximum // difference after removing one element const findMinDifference = (arr, n) => { // taking variables to store 2 max and 2 min // elements let firstmin = Number.MAX_SAFE_INTEGER; let secondmin = Number.MAX_SAFE_INTEGER; let firstmax = Number.MIN_SAFE_INTEGER; let secondmax = Number.MIN_SAFE_INTEGER; // iterating over array for (let i = 0; i < n; i++) { // if found min element than firstmin if (arr[i] < firstmin) { secondmin = firstmin; firstmin = arr[i]; } else if (arr[i] < secondmin) { secondmin = arr[i]; } if (arr[i] > firstmax) { secondmax = firstmax; firstmax = arr[i]; // if found element greater than second max } else if (arr[i] > secondmax) { secondmax = arr[i]; } } // returning answer return Math.min(secondmax - firstmin, firstmax - secondmin); } const arr = [1, 3, 4, 7]; const n = arr.length; console.log(findMinDifference(arr, n)); |
C#
// C# program for the above approach using System; public class GFG{ // Function to find the minimum maximum // difference after removing one element public static int findMinDifference( int [] arr, int n) { //taking variables to store 2 max and 2 min elements int firstmin = int .MaxValue; int secondmin = int .MaxValue; int firstmax = int .MinValue; int secondmax = int .MinValue; //iterating over array for ( int i = 0;i < n;i++) { //if found min element than firstmin if (arr[i] < firstmin) { //updating secondmin secondmin = firstmin; //updating firstmin firstmin = arr[i]; } //if found element small than secondmin else if (arr[i] < secondmin) { secondmin = arr[i]; } //if found element larger than firstmax if (arr[i] > firstmax) { //updating second max secondmax = firstmax; //updating first max firstmax = arr[i]; } //if found element greater than second max else if (arr[i] > secondmax) { secondmax = arr[i]; } } //returning answer return Math.Min(secondmax - firstmin,firstmax - secondmin); } // Driver Code internal static void Main() { int [] arr = {1, 3, 4, 7}; int N = arr.Length; Console.Write(findMinDifference(arr, N)); } //This code is contributed by bhardwajji } |
3
Time Complexity:- O(N)
Auxiliary Space:- O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!