Given an sorted array arr[] consisting of N elements, the task is to find the minimum of all maximum differences between adjacent elements of all arrays obtained by removal of any single array element.
Examples:
Input: arr[ ] = { 1, 3, 7, 8}
Output: 5
Explanation:
All possible arrays after removing a single element are as follows:
{3, 7, 8}: Difference between adjacent elements are { 4, 1}. Maximum = 4.
{ 1, 7, 8}: Difference between adjacent elements are { 6, 1}. Maximum = 6.
{ 1, 3, 8}: Difference between adjacent elements are { 2, 5}. Maximum = 5.
Finally, minimum of (4, 6, 5) is 4, which is the required output.Input: arr[ ] = { 1, 2, 3, 4, 5}
Output: 1
Explanation:
All possible arrays after removing a single element are as follows:
{ 2, 3, 4, 5}: Difference between adjacent elements are { 1, 1, 1}. Maximum = 1.
{ 1, 3, 4, 5}: Difference between adjacent elements are { 2, 1, 1}. Maximum = 2.
{ 1, 2, 4, 5}: Difference between adjacent elements are { 1, 2, 1}. Maximum = 2.
{ 1, 2, 3, 5}: Difference between adjacent elements are { 1, 1, 2}. Maximum = 2.
Finally, minimum of (1, 2, 2, 2) is 1, which is the required output.
Approach: Follow the steps to solve the problem
- Declare a variable MinValue = INT_MAX to store the final answer.
- Traverse the array, for i in range [0, N – 1]
- Declare a vector new_arr which is a copy of arr[] except element arr[i]
- Store the maximum adjacent difference of new_arr in a variable diff
- Update MinValue = min(MinValue, diff)
- Return MinValue as the final answer.
Below is the implementation of above approach.
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum difference// between adjacent array elementsint maxAdjacentDifference(vector<int> A){ // Store the maximum difference int diff = 0;// Traverse the array for (int i = 1; i < (int)A.size(); i++) { // Update maximum difference diff = max(diff, A[i] - A[i - 1]); } return diff;}// Function to calculate the minimum// of maximum difference between// adjacent array elements possible// by removing a single array elementint MinimumValue(int arr[], int N){ // Stores the required minimum int MinValue = INT_MAX; for (int i = 0; i < N; i++) { // Stores the updated array vector<int> new_arr; for (int j = 0; j < N; j++) { // Skip the i-th element if (i == j) continue; new_arr.push_back(arr[j]); } // Update MinValue MinValue = min(MinValue, maxAdjacentDifference(new_arr)); } // return MinValue return MinValue;}// Driver Codeint main(){ int arr[] = { 1, 3, 7, 8 }; int N = sizeof(arr) / sizeof(int); cout << MinimumValue(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG {// Function to find maximum difference// between adjacent array elementsstatic int maxAdjacentDifference(ArrayList<Integer> A){ // Store the maximum difference int diff = 0;// Traverse the array for (int i = 1; i < (int)A.size(); i++) { // Update maximum difference diff = Math.max(diff, A.get(i) - A.get(i - 1)); } return diff;}// Function to calculate the minimum// of maximum difference between// adjacent array elements possible// by removing a single array elementstatic int MinimumValue(int arr[], int N){ // Stores the required minimum int MinValue = Integer.MAX_VALUE; for (int i = 0; i < N; i++) { // Stores the updated array ArrayList<Integer> new_arr=new ArrayList<>(); for (int j = 0; j < N; j++) { // Skip the i-th element if (i == j) continue; new_arr.add(arr[j]); } // Update MinValue MinValue = Math.min(MinValue, maxAdjacentDifference(new_arr)); } // return MinValue return MinValue;} // Driver code public static void main (String[] args) { int arr[] = { 1, 3, 7, 8 }; int N = arr.length; System.out.print(MinimumValue(arr, N)); }}// This code is contributed by offbeat |
Python3
# Python3 program to implement# the above approachimport sys# Function to find maximum difference# between adjacent array elementsdef maxAdjacentDifference(A): # Store the maximum difference diff = 0 # Traverse the array for i in range(1, len(A), 1): # Update maximum difference diff = max(diff, A[i] - A[i - 1]) return diff# Function to calculate the minimum# of maximum difference between# adjacent array elements possible# by removing a single array elementdef MinimumValue(arr, N): # Stores the required minimum MinValue = sys.maxsize for i in range(N): # Stores the updated array new_arr = [] for j in range(N): # Skip the i-th element if (i == j): continue new_arr.append(arr[j]) # Update MinValue MinValue = min(MinValue, maxAdjacentDifference(new_arr)) # return MinValue return MinValue# Driver Codeif __name__ == '__main__': arr = [ 1, 3, 7, 8 ] N = len(arr) print(MinimumValue(arr, N))# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Function to find maximum difference// between adjacent array elementsstatic int maxAdjacentDifference(List<int> A){ // Store the maximum difference int diff = 0; // Traverse the array for(int i = 1; i < A.Count; i++) { // Update maximum difference diff = Math.Max(diff, A[i] - A[i - 1]); } return diff;}// Function to calculate the minimum// of maximum difference between// adjacent array elements possible// by removing a single array elementstatic int MinimumValue(int[] arr, int N){ // Stores the required minimum int MinValue = Int32.MaxValue; for(int i = 0; i < N; i++) { // Stores the updated array List<int> new_arr = new List<int>(); for(int j = 0; j < N; j++) { // Skip the i-th element if (i == j) continue; new_arr.Add(arr[j]); } // Update MinValue MinValue = Math.Min(MinValue, maxAdjacentDifference(new_arr)); } // Return MinValue return MinValue;}// Driver Codepublic static void Main(string[] args){ int[] arr = { 1, 3, 7, 8 }; int N = arr.Length; Console.WriteLine(MinimumValue(arr, N));}}// This code is contributed by ukasp |
Javascript
<script>// JavaScript program to implement// the above approach// Function to find maximum difference// between adjacent array elementsfunction maxAdjacentDifference(A){ // Store the maximum difference let diff = 0; // Traverse the array for (let i = 1; i < A.length; i++) { // Update maximum difference diff = Math.max(diff, A[i] - A[i-1]); } return diff;} // Function to calculate the minimum// of maximum difference between// adjacent array elements possible// by removing a single array elementfunction MinimumValue(arr, N){ // Stores the required minimum let MinValue = Number.MAX_VALUE; for (let i = 0; i < N; i++) { // Stores the updated array let new_arr=[]; for (let j = 0; j < N; j++) { // Skip the i-th element if (i == j) continue; new_arr.push(arr[j]); } // Update MinValue MinValue = Math.min(MinValue, maxAdjacentDifference(new_arr)); } // return MinValue return MinValue; }// Driver code let arr = [ 1, 3, 7, 8 ]; let N = arr.length; document.write(MinimumValue(arr, N)); </script> |
Output:
4
Time Complexity : O(N2)
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!
