Minimize the maximum minimum difference after one removal from array
Given an array arr[] of size n ? 3, the task is to find the minimum possible difference between the maximum and the minimum element from the array after removing one element.
Examples:
Input: arr[] = {1, 2, 3}
Output: 1
Removing 1 will give 3 – 2 = 1
Removing 2, 3 – 1 = 2
And removing 3 will result in 2 – 1 = 1Input: arr[] = {1, 2, 4, 3, 4}
Output: 2
Naive Approach: It is clear that to have an effect on the difference only the minimum or the maximum element has to be removed.
- Sort the array.
- Remove the minimum, store diff1 = arr[n – 1] – arr[1].
- Remove the maximum, and diff2 = arr[n – 2] – arr[0].
- Print min(diff1, diff2) in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum required differenceint findMinDifference(int arr[], int n){ // Sort the given array sort(arr, arr + n); // When minimum element is removed int diff1 = arr[n - 1] - arr[1]; // When maximum element is removed int diff2 = arr[n - 2] - arr[0]; // Return the minimum of diff1 and diff2 return min(diff1, diff2);}// Driver Codeint main(){ int arr[] = { 1, 2, 4, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findMinDifference(arr, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class solution{// Function to return the minimum required differencestatic int findMinDifference(int arr[], int n){ // Sort the given array Arrays.sort(arr); // When minimum element is removed int diff1 = arr[n - 1] - arr[1]; // When maximum element is removed int diff2 = arr[n - 2] - arr[0]; // Return the minimum of diff1 and diff2 return Math.min(diff1, diff2);}// Driver Codepublic static void main(String args[]){ int arr[] = { 1, 2, 4, 3, 4 }; int n = arr.length; System.out.print(findMinDifference(arr, n));}}// This code is contributed by// Sanjit_Prasad |
Python3
# Python3 implementation of the approach # Function to return the minimum# required difference def findMinDifference(arr, n) : # Sort the given array arr.sort() # When minimum element is removed diff1 = arr[n - 1] - arr[1] # When maximum element is removed diff2 = arr[n - 2] - arr[0] # Return the minimum of diff1 and diff2 return min(diff1, diff2) # Driver Code if __name__ == "__main__" : arr = [ 1, 2, 4, 3, 4 ] n = len(arr) print(findMinDifference(arr, n)) # This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;public class GFG{ // Function to return the minimum required differencestatic int findMinDifference(int []arr, int n){ // Sort the given array Array.Sort(arr); // When minimum element is removed int diff1 = arr[n - 1] - arr[1]; // When maximum element is removed int diff2 = arr[n - 2] - arr[0]; // Return the minimum of diff1 and diff2 return Math.Min(diff1, diff2);}// Driver Code static public void Main (){ int []arr = { 1, 2, 4, 3, 4 }; int n = arr.Length; Console.Write(findMinDifference(arr, n));}}// This code is contributed by Sachin.. |
PHP
<?php// PHP implementation of the approach// Function to return the minimum // required differencefunction findMinDifference($arr, $n){ // Sort the given array sort($arr, 0); // When minimum element is removed $diff1 = $arr[$n - 1] - $arr[1]; // When maximum element is removed $diff2 = $arr[$n - 2] - $arr[0]; // Return the minimum of diff1 and diff2 return min($diff1, $diff2);}// Driver Code$arr = array(1, 2, 4, 3, 4);$n = sizeof($arr);echo findMinDifference($arr, $n);// This code is contributed// by Akanksha Rai |
Javascript
<script> // Javascript implementation of the approach // Function to return the minimum required difference function findMinDifference(arr, n) { // Sort the given array arr.sort(); // When minimum element is removed let diff1 = arr[n - 1] - arr[1]; // When maximum element is removed let diff2 = arr[n - 2] - arr[0]; // Return the minimum of diff1 and diff2 return Math.min(diff1, diff2); } let arr = [ 1, 2, 4, 3, 4 ]; let n = arr.length; document.write(findMinDifference(arr, n)); </script> |
Output
2
Complexity Analysis:
- Time Complexity: O(nlogn)
- Auxiliary Space : O(1)
Efficient Approach: In order to find the min, secondMin, max and secondMax elements from the array. We don’t need to sort the array, it can be done in a single array traversal.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include<bits/stdc++.h>using namespace std;// Function to return the minimum required differenceint findMinDifference(int arr[], int n){ int min__, secondMin, max__, secondMax; min__ = secondMax = (arr[0] < arr[1]) ? arr[0] : arr[1]; max__ = secondMin = (arr[0] < arr[1]) ? arr[1] : arr[0]; for (int i = 2; i < n; i++) { // If current element is greater than max if (arr[i] > max__) { // max will become secondMax secondMax = max__; // Update the max max__ = arr[i]; } // If current element is greater than secondMax // but smaller than max else if (arr[i] > secondMax) { // Update the secondMax secondMax = arr[i]; } // If current element is smaller than min else if (arr[i] < min__) { // min will become secondMin secondMin = min__; // Update the min min__ = arr[i]; } // If current element is smaller than secondMin // but greater than min else if (arr[i] < secondMin) { // Update the secondMin secondMin = arr[i]; } } // Minimum of the two possible differences int diff = min(max__ - secondMin, secondMax - min__); return diff;}// Driver codeint main(){ int arr[] = { 1, 2, 4, 3, 4 }; int n = sizeof(arr)/sizeof(arr[0]); cout << (findMinDifference(arr, n));} // This code is contributed by// Shashank_Sharma |
Java
// Java implementation of the approachpublic class GFG { // Function to return the minimum required difference static int findMinDifference(int arr[], int n) { int min, secondMin, max, secondMax; min = secondMax = (arr[0] < arr[1]) ? arr[0] : arr[1]; max = secondMin = (arr[0] < arr[1]) ? arr[1] : arr[0]; for (int i = 2; i < n; i++) { // If current element is greater than max if (arr[i] > max) { // max will become secondMax secondMax = max; // Update the max max = arr[i]; } // If current element is greater than secondMax // but smaller than max else if (arr[i] > secondMax) { // Update the secondMax secondMax = arr[i]; } // If current element is smaller than min else if (arr[i] < min) { // min will become secondMin secondMin = min; // Update the min min = arr[i]; } // If current element is smaller than secondMin // but greater than min else if (arr[i] < secondMin) { // Update the secondMin secondMin = arr[i]; } } // Minimum of the two possible differences int diff = Math.min(max - secondMin, secondMax - min); return diff; } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 4, 3, 4 }; int n = arr.length; System.out.println(findMinDifference(arr, n)); }} |
Python3
# Python 3 implementation of the approach# Function to return the minimum# required differencedef findMinDifference(arr, n): if(arr[0] < arr[1]): min__ = secondMax = arr[0] else: min__ = secondMax = arr[1] if(arr[0] < arr[1]): max__ = secondMin = arr[1] else: max__ = secondMin = arr[0] for i in range(2, n): # If current element is greater # than max if (arr[i] > max__): # max will become secondMax secondMax = max__ # Update the max max__ = arr[i] # If current element is greater than # secondMax but smaller than max elif (arr[i] > secondMax): # Update the secondMax secondMax = arr[i] # If current element is smaller than min elif(arr[i] < min__): # min will become secondMin secondMin = min__ # Update the min min__ = arr[i] # If current element is smaller than # secondMin but greater than min elif(arr[i] < secondMin): # Update the secondMin secondMin = arr[i] # Minimum of the two possible # differences diff = min(max__ - secondMin, secondMax - min__) return diff# Driver codeif __name__ == '__main__': arr = [1, 2, 4, 3, 4] n = len(arr) print(findMinDifference(arr, n))# This code is contributed by# Surendra_Gangwar |
C#
using System; // C# implementation of the approach public class GFG { // Function to return the minimum required difference static int findMinDifference(int []arr, int n) { int min, secondMin, max, secondMax; min = secondMax = (arr[0] < arr[1]) ? arr[0] : arr[1]; max = secondMin = (arr[0] < arr[1]) ? arr[1] : arr[0]; for (int i = 2; i < n; i++) { // If current element is greater than max if (arr[i] > max) { // max will become secondMax secondMax = max; // Update the max max = arr[i]; } // If current element is greater than secondMax // but smaller than max else if (arr[i] > secondMax) { // Update the secondMax secondMax = arr[i]; } // If current element is smaller than min else if (arr[i] < min) { // min will become secondMin secondMin = min; // Update the min min = arr[i]; } // If current element is smaller than secondMin // but greater than min else if (arr[i] < secondMin) { // Update the secondMin secondMin = arr[i]; } } // Minimum of the two possible differences int diff = Math.Min(max - secondMin, secondMax - min); return diff; } // Driver code public static void Main() { int []arr = { 1, 2, 4, 3, 4 }; int n = arr.Length; Console.WriteLine(findMinDifference(arr, n)); } } // This code is contributed by 29AjayKumar |
PHP
<?php// PHP implementation of the approach// Function to return the minimum// required differencefunction findMinDifference($arr, $n){ $min__ = $secondMax = ($arr[0] < $arr[1]) ? $arr[0] : $arr[1]; $max__ = $secondMin = ($arr[0] < $arr[1]) ? $arr[1] : $arr[0]; for ($i = 2; $i < $n; $i++) { // If current element is greater than max if ($arr[$i] > $max__) { // max will become secondMax $secondMax = $max__; // Update the max $max__ = $arr[$i]; } // If current element is greater than secondMax // but smaller than max else if ($arr[$i] > $secondMax) { // Update the secondMax $secondMax = $arr[$i]; } // If current element is smaller than min else if ($arr[$i] < $min__) { // min will become secondMin $secondMin = $min__; // Update the min $min__ = $arr[$i]; } // If current element is smaller than secondMin // but greater than min else if ($arr[$i] < $secondMin) { // Update the secondMin $secondMin = $arr[$i]; } } // Minimum of the two possible differences $diff = min($max__ - $secondMin, $secondMax - $min__); return $diff;}// Driver code$arr = array( 1, 2, 4, 3, 4 );$n = count($arr);print(findMinDifference($arr, $n));// This code is contributed by mits?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the minimum required difference function findMinDifference(arr, n) { let min__, secondMin, max__, secondMax; min__ = secondMax = (arr[0] < arr[1]) ? arr[0] : arr[1]; max__ = secondMin = (arr[0] < arr[1]) ? arr[1] : arr[0]; for (let i = 2; i < n; i++) { // If current element is greater than max if (arr[i] > max__) { // max will become secondMax secondMax = max__; // Update the max max__ = arr[i]; } // If current element is greater than secondMax // but smaller than max else if (arr[i] > secondMax) { // Update the secondMax secondMax = arr[i]; } // If current element is smaller than min else if (arr[i] < min__) { // min will become secondMin secondMin = min__; // Update the min min__ = arr[i]; } // If current element is smaller than secondMin // but greater than min else if (arr[i] < secondMin) { // Update the secondMin secondMin = arr[i]; } } // Minimum of the two possible differences let diff = Math.min(max__ - secondMin, secondMax - min__); return diff; } let arr = [ 1, 2, 4, 3, 4 ]; let n = arr.length; document.write(findMinDifference(arr, n)); </script> |
Output
2
Complexity Analysis:
- Time Complexity: O(n), to traverse an array of size n
- Auxiliary Space: O(1), as no extra space is used
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
