Given an array arr[] of N integers, the task is to find the maximum absolute difference between distinct elements of the array.
Examples:
Input: arr[] = {12, 10, 9, 45, 2, 10, 10, 45, 10}
Output: 10
Explanation:
Distinct elements of given array are 12, 9, 2.
Therefore, the maximum absolute difference between them is (12 – 2) = 10.Input: arr[] = {2, -1, 10, 3, -2, -1, 10}
Output: 5
Explanation:
Distinct elements of given array are 2, 3, -2.
Therefore, the maximum absolute difference between them is (3 – (-2)) = 5.
Naive Approach: The naive approach is to store the distinct element in the given array in an array temp[] and print the difference of maximum and minimum element of the array temp[].
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The above naive approach can be optimized using Hashing. Below are the steps:
- Store the frequency of each element of the array arr[] in a HashMap.
- Now find the maximum and minimum value of the array whose frequency is 1 using the above HashMap created.
- Print the difference between the maximum and minimum value obtained in the above step.
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 maximum// absolute difference between// distinct elements in arr[]int MaxAbsDiff(int arr[], int n){ // Map to store each element // with their occurrence in array unordered_map<int, int> map; // maxElement and minElement to // store maximum and minimum // distinct element in arr[] int maxElement = INT_MIN; int minElement = INT_MAX; // Traverse arr[] and update each // element frequency in Map for(int i = 0; i < n; i++) { map[arr[i]]++; } // Traverse Map and check if // value of any key appears 1 // then update maxElement and // minElement by that key for(auto itr = map.begin(); itr != map.end(); itr++) { if (itr -> second == 1) { maxElement = max(maxElement, itr -> first); minElement = min(minElement, itr -> first); } } // Return absolute difference of // maxElement and minElement return abs(maxElement - minElement);}// Driver Codeint main(){ // Given array arr[] int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45, 10 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << MaxAbsDiff(arr, n) << "\n"; return 0;}// This code is contributed by akhilsaini |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find the maximum // absolute difference between // distinct elements in arr[] static int MaxAbsDiff(int[] arr, int n) { // HashMap to store each element // with their occurrence in array Map<Integer, Integer> map = new HashMap<>(); // maxElement and minElement to // store maximum and minimum // distinct element in arr[] int maxElement = Integer.MIN_VALUE; int minElement = Integer.MAX_VALUE; // Traverse arr[] and update each // element frequency in HashMap for (int i = 0; i < n; i++) { map.put(arr[i], map.getOrDefault(arr[i], 0) + 1); } // Traverse HashMap and check if // value of any key appears 1 // then update maxElement and // minElement by that key for (Map.Entry<Integer, Integer> k : map.entrySet()) { if (k.getValue() == 1) { maxElement = Math.max(maxElement, k.getKey()); minElement = Math.min(minElement, k.getKey()); } } // Return absolute difference of // maxElement and minElement return Math.abs(maxElement - minElement); } // Driver Code public static void main(String[] args) { // Given array arr[] int[] arr = { 12, 10, 9, 45, 2, 10, 10, 45, 10 }; int n = arr.length; // Function Call System.out.println(MaxAbsDiff(arr, n)); }} |
Python3
# Python3 program for # the above approachimport sysfrom collections import defaultdict# Function to find the maximum# absolute difference between# distinct elements in arr[]def MaxAbsDiff(arr, n): # HashMap to store each element # with their occurrence in array map = defaultdict (int) # maxElement and minElement to # store maximum and minimum # distinct element in arr[] maxElement = -sys.maxsize - 1 minElement = sys.maxsize # Traverse arr[] and update each # element frequency in HashMap for i in range (n): map[arr[i]] += 1 # Traverse HashMap and check if # value of any key appears 1 # then update maxElement and # minElement by that key for k in map: if (map[k] == 1): maxElement = max(maxElement, k) minElement = min(minElement, k) # Return absolute difference of # maxElement and minElement return abs(maxElement - minElement)# Driver Codeif __name__ == "__main__": # Given array arr[] arr = [12, 10, 9, 45, 2, 10, 10, 45, 10] n = len( arr) # Function Call print(MaxAbsDiff(arr, n))# This code is contributed by Chitranayal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the maximum// absolute difference between// distinct elements in []arrstatic int MaxAbsDiff(int[] arr, int n){ // Dictionary to store each element // with their occurrence in array Dictionary<int, int> map = new Dictionary<int, int>(); // maxElement and minElement to // store maximum and minimum // distinct element in []arr int maxElement = int.MinValue; int minElement = int.MaxValue; // Traverse []arr and update each // element frequency in Dictionary for(int i = 0; i < n; i++) { if(map.ContainsKey(arr[i])) map[arr[i]] = map[arr[i]] + 1; else map.Add(arr[i], 1); } // Traverse Dictionary and check if // value of any key appears 1 // then update maxElement and // minElement by that key foreach (KeyValuePair<int, int> k in map) { if (k.Value == 1) { maxElement = Math.Max(maxElement, k.Key); minElement = Math.Min(minElement, k.Key); } } // Return absolute difference of // maxElement and minElement return Math.Abs(maxElement - minElement);}// Driver Codepublic static void Main(String[] args){ // Given array []arr int[] arr = { 12, 10, 9, 45, 2, 10, 10, 45, 10 }; int n = arr.Length; // Function call Console.WriteLine(MaxAbsDiff(arr, n));}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum// absolute difference between// distinct elements in arr[]function MaxAbsDiff(arr, n){ // Map to store each element // with their occurrence in array var map = new Map(); // maxElement and minElement to // store maximum and minimum // distinct element in arr[] var maxElement = -1000000000; var minElement = 1000000000; // Traverse arr[] and update each // element frequency in Map for(var i = 0; i < n; i++) { if(map.has(arr[i])) map.set(arr[i], map.get(arr[i])+1) else map.set(arr[i], 1); } // Traverse Map and check if // value of any key appears 1 // then update maxElement and // minElement by that key map.forEach((value, key) => { if (value == 1) { maxElement = Math.max(maxElement, key); minElement = Math.min(minElement, key); } }); // Return absolute difference of // maxElement and minElement return Math.abs(maxElement - minElement);}// Driver Code// Given array arr[]var arr = [12, 10, 9, 45, 2, 10, 10, 45, 10 ];var n = arr.length;// Function calldocument.write( MaxAbsDiff(arr, n));// This code is contributed by famously.</script> |
Output:
10
Time Complexity: O(N)
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!
