Minimize the maximum minimum difference after one removal from array

0 0 9 minutes read

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 = 1

Input: 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 difference
int 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 Code
int 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 approach
import java.util.*;
 
class solution
{
 
// Function to return the minimum required difference
static 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 Code
public 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 approach
using System;
 
public class GFG{
     
// Function to return the minimum required difference
static 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 difference
function 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

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.