Maximum difference between a pair of adjacent elements by excluding every element once
Given an array arr[] consisting of positive integers, the task for every array element is to find the maximum difference between any two adjacent arrays excluding that element.
Examples:
Input: arr[] = {1, 3, 4, 7, 8}
Output: 3, 4, 4
Explanation:
Excluding i = 2, arr[] = {1, 4, 7, 8}. Therefore, the maximum adjacent element difference is 3.
Excluding i = 3, arr[] = {1, 3, 7, 8}. Therefore, the maximum adjacent element difference is 4.
Excluding i = 4, arr[] = {1, 3, 4, 8}. Therefore, the maximum adjacent element difference is 4.Input: arr[] = {1, 2, 7}
Output: 6
Naive Approach: The simplest approach is to use traverse the array and, for every element, calculate the difference between adjacent elements excluding that element, and print the maximum difference obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate maximum // difference between adjacent elements // excluding every array element once void maxAdjacent( int * arr, int N) { vector< int > res; // Traverse the array for ( int i = 1; i < N - 1; i++) { int prev = arr[0]; // Stores the maximum diff int maxi = INT_MIN; // Check for maximum // adjacent element for ( int j = 1; j < N; j++) { // Exclude current element if (i == j) continue ; // Update maximum difference maxi = max(maxi, abs (arr[j] - prev)); // Update previous value prev = arr[j]; } // Append the result // into a vector res.push_back(maxi); } // Print the result for ( auto x : res) cout << x << " " ; cout << endl; } // Driver Code int main() { int arr[] = { 1, 3, 4, 7, 8 }; int N = sizeof (arr) / sizeof (arr[0]); maxAdjacent(arr, N); } |
Java
// Java implementation of above approach import java.util.*; class GFG { // Function to calculate maximum // difference between adjacent elements // excluding every array element once static void maxAdjacent( int [] arr, int N) { ArrayList<Integer> res = new ArrayList<Integer>(); // Traverse the array for ( int i = 1 ; i < N - 1 ; i++) { int prev = arr[ 0 ]; // Stores the maximum diff int maxi = Integer.MIN_VALUE; // Check for maximum // adjacent element for ( int j = 1 ; j < N; j++) { // Exclude current element if (i == j) continue ; // Update maximum difference maxi = Math.max(maxi, Math.abs(arr[j] - prev)); // Update previous value prev = arr[j]; } // Append the result // into a vector res.add(maxi); } // Print the result for ( int x : res) { System.out.print(x + " " ); } System.out.println(); } // Driver code public static void main(String[] args) { int [] arr = { 1 , 3 , 4 , 7 , 8 }; int N = arr.length; maxAdjacent(arr, N); } } // This code is contributed by sanjoy_62. |
Python3
# Python program for the above approach # Function to calculate maximum # difference between adjacent elements # excluding every array element once def maxAdjacent(arr, N): res = [] # Traverse the array for i in range ( 1 , N - 1 ): prev = arr[ 0 ] # Stores the maximum diff maxi = - 1 * float ( 'inf' ) # Check for maximum # adjacent element for j in range ( 1 ,N): # Exclude current element if (i = = j): continue # update maximum difference maxi = max (maxi, abs (arr[j] - prev)) # Update previous value prev = arr[j] # Append the result # into a vector res.append(maxi) # Print the result for x in res: print (x,end = ' ' ) print () # Driver Code arr = [ 1 , 3 , 4 , 7 , 8 ] N = len (arr) maxAdjacent(arr, N) # This code is contributed by rohitsingh07052. |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to calculate maximum // difference between adjacent elements // excluding every array element once static void maxAdjacent( int [] arr, int N) { List< int > res = new List< int >(); // Traverse the array for ( int i = 1; i < N - 1; i++) { int prev = arr[0]; // Stores the maximum diff int maxi = Int32.MinValue; // Check for maximum // adjacent element for ( int j = 1; j < N; j++) { // Exclude current element if (i == j) continue ; // Update maximum difference maxi = Math.Max(maxi, Math.Abs(arr[j] - prev)); // Update previous value prev = arr[j]; } // Append the result // into a vector res.Add(maxi); } // Print the result foreach ( int x in res) { Console.Write(x + " " ); } Console.WriteLine(); } // Driver Code static public void Main () { int [] arr = { 1, 3, 4, 7, 8 }; int N = arr.Length; maxAdjacent(arr, N); } } // This code is contributed by code_hunt. |
Javascript
<script> //Javascript program for //the above approach // Function to calculate maximum // difference between adjacent elements // excluding every array element once function maxAdjacent(arr, N) { var res = []; // Traverse the array for ( var i = 1; i < N - 1; i++) { var prev = arr[0]; // Stores the maximum diff var maxi = Number.MIN_VALUE; // Check for maximum // adjacent element for ( var j = 1; j < N; j++) { // Exclude current element if (i == j) continue ; // Update maximum difference maxi = Math.max(maxi, Math.abs(arr[j] - prev)); // Update previous value prev = arr[j]; } // Append the result // into a vector res.push(maxi); } // Print the result for ( var j = 0; j < res.length; j++) document.write(res[j] + " " ); document.write( "<br>" ); } var arr = [ 1, 3, 4, 7, 8 ]; var N = arr.length; maxAdjacent(arr, N); // This code is contributed by SoumikMondal </script> |
3 4 4
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Method: It can be clearly observed that if an element is excluded from the array, then the maximum difference either remains the same or will become equal to the difference between the next and previous of the excluded element. Follow the steps below to solve the problem:
- Calculate the maximum difference between adjacent elements of the array.
- Traverse the array and perform the following operations:
- Evaluate the difference between the previous and the array element next to the excluded element.
- If the maximum adjacent difference calculated exceeds the difference obtained in the previous step, insert the maximum adjacent difference for the whole array into the vector res.
- Otherwise, insert the difference between the previous and the array element next to the excluded element into the vector res.
- Print the vector res.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate maximum // difference between adjacent elements // excluding every array element once void maxAdjacent( int * arr, int N) { vector< int > res; int arr_max = INT_MIN; // Compute maximum adjacent // difference for whole array for ( int i = 1; i < N; i++) { arr_max = max(arr_max, abs (arr[i - 1] - arr[i])); } for ( int i = 1; i < N - 1; i++) { int curr_max = abs (arr[i - 1] - arr[i + 1]); // Store the maximum between // arr_max and curr_max int ans = max(curr_max, arr_max); // Append the result // into a vector res.push_back(ans); } // Print the result for ( auto x : res) cout << x << " " ; cout << endl; } // Driver Code int main() { int arr[] = { 1, 3, 4, 7, 8 }; int N = sizeof (arr) / sizeof (arr[0]); maxAdjacent(arr, N); } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to calculate maximum // difference between adjacent elements // excluding every array element once static void maxAdjacent( int []arr, int N) { Vector<Integer> res = new Vector<Integer>(); int arr_max = Integer.MIN_VALUE; // Compute maximum adjacent // difference for whole array for ( int i = 1 ; i < N; i++) { arr_max = Math.max(arr_max, Math.abs(arr[i - 1 ] - arr[i])); } for ( int i = 1 ; i < N - 1 ; i++) { int curr_max = Math.abs(arr[i - 1 ] - arr[i + 1 ]); // Store the maximum between // arr_max and curr_max int ans = Math.max(curr_max, arr_max); // Append the result // into a vector res.add(ans); } // Print the result for ( int x : res) System.out.print(x + " " ); System.out.println(); } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 3 , 4 , 7 , 8 }; int N = arr.length; maxAdjacent(arr, N); } } // This code is contributed by shikhasingrajput |
Python3
# Python 3 program for the above approach import sys # Function to calculate maximum # difference between adjacent elements # excluding every array element once def maxAdjacent(arr, N): res = [] arr_max = - sys.maxsize - 1 # Compute maximum adjacent # difference for whole array for i in range ( 1 , N): arr_max = max (arr_max, abs (arr[i - 1 ] - arr[i])) for i in range ( 1 , N - 1 ): curr_max = abs (arr[i - 1 ] - arr[i + 1 ]) # Store the maximum between # arr_max and curr_max ans = max (curr_max, arr_max) # Append the result # into a vector res.append(ans) # Print the result for x in res: print (x, end = " " ) print () # Driver Code if __name__ = = "__main__" : arr = [ 1 , 3 , 4 , 7 , 8 ] N = len (arr) maxAdjacent(arr, N) # This code is contributed by chitranayal. |
C#
// C# Program to implement // the above approach using System; using System.Collections.Generic; class GFG { // Function to calculate maximum // difference between adjacent elements // excluding every array element once static void maxAdjacent( int []arr, int N) { List< int > res = new List< int >(); int arr_max = Int32.MinValue; // Compute maximum adjacent // difference for whole array for ( int i = 1; i < N; i++) { arr_max = Math.Max(arr_max, Math.Abs(arr[i - 1] - arr[i])); } for ( int i = 1; i < N - 1; i++) { int curr_max = Math.Abs(arr[i - 1] - arr[i + 1]); // Store the maximum between // arr_max and curr_max int ans = Math.Max(curr_max, arr_max); // Append the result // into a vector res.Add(ans); } // Print the result foreach ( int x in res) Console.Write(x + " " ); Console.WriteLine(); } // Driver Code public static void Main(String[] args) { int [] arr = { 1, 3, 4, 7, 8 }; int N = arr.Length; maxAdjacent(arr, N); } } // This code is contributed by susmitakundugoaldanga. |
Javascript
<script> // Javascript program for the above approach // Function to calculate maximum // difference between adjacent elements // excluding every array element once function maxAdjacent(arr,N) { let res = []; let arr_max = Number.MIN_VALUE; // Compute maximum adjacent // difference for whole array for (let i = 1; i < N; i++) { arr_max = Math.max(arr_max, Math.abs(arr[i - 1] - arr[i])); } for (let i = 1; i < N - 1; i++) { let curr_max = Math.abs(arr[i - 1] - arr[i + 1]); // Store the maximum between // arr_max and curr_max let ans = Math.max(curr_max, arr_max); // Append the result // into a vector res.push(ans); } // Print the result document.write(res.join( " " )); } // Driver Code let arr=[1, 3, 4, 7, 8]; let N = arr.length; maxAdjacent(arr, N); // This code is contributed by avanitrachhadiya2155 </script> |
3 4 4
Time Complexity: O(N)
Auxiliary Space: O(1)