An array is the most efficient data structure that is designed to store and access a group of objects. Given an array of integers, our task is to find out two elements from that array such that the difference between them is the maximum.
We will be discussing two approaches:
- By comparing and checking the difference between every possible pair by running two loops.
- By calculating the min and max values of the array and returning the difference between them.
Input : arr = {2, 3, 10, 6, 4, 8, 1}
Output : Two elements with largest difference: 10 and 1
Explanation : The maximum difference is between 10 and 1.
Input : arr = {-7, 9, 5, 6, 3, 2}
Output : Two elements with largest difference: 9 and -7
Explanation : The maximum difference is between 9 and -7.
Input : arr = {10, 11, 88, 2, 12, 120}
Output : Two elements with largest difference: 2 and 120
Explanation : The maximum difference is between 2 and 120.
Method 1: By comparing and checking the difference between every possible pair by running two loops
- Use two loops. In the outer loop, pick elements one by one, and in the inner loop calculate the difference of the picked element with every other element in the array.
- And simultaneously compare the difference with the maximum difference calculated so far.
- Check for all possible differences between any 2 elements in the array and finally select the elements whose difference is the largest.
Below is the implementation of the above approach :
Java
// Java Program to Find 2// Elements in an array// such that the difference// between them is the largestimport java.io.*;class Largest_Difference_GFG { public static int[] Maximum_Diff(int a[], int n) { int diff, greatest_diff = a[1] - a[0]; int ele1 = a[1], ele2 = a[0]; // Array to store the difference and the // two elements ele1 and ele2 . int res[] = new int[3]; // Check for all possible difference between // any 2 elements in the array and finally select // the elements whose difference is the largest for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { diff = Math.abs(a[i] - a[j]); if (diff > greatest_diff) { greatest_diff = diff; ele1 = a[i]; ele2 = a[j]; } } } res[0] = greatest_diff; res[1] = ele1; res[2] = ele2; return (res); } public static void main(String[] args) { int arr[] = { 10, 11, 88, 2, 12, 120 }; int size = arr.length; int[] result; result = Largest_Difference_GFG.Maximum_Diff(arr, size); System.out.println("Greatest Difference:" + result[0]); System.out.println( "Two elements with largest difference: " + result[1] + " and " + result[2]); }} |
Greatest Difference:118 Two elements with largest difference: 2 and 120
- Time Complexity: O(n^2)
- Auxiliary Space: O(1)
Method 2: By calculating the min and max values of the array and returning the difference between them
- The Largest difference between 2 elements in an array will be always the absolute difference between the smallest and largest element present in that array.
- Using 2 independent for loops, determine the min and max element of the array. Below is the implementation of the above approach :
Java
// Java Program to Find 2// Elements in an array// such that the difference// between them is the largestimport java.util.*;class GFG { public static void main(String args[]) { int array[] = new int[] { 10, 11, 88, 2, 12, 120 }; int len = array.length; Arrays.sort(array); // sorting the array int max_diff = array[len - 1] - array[0]; System.out.println("Maximum Difference is: " + max_diff); System.out.println( "Two elements with largest difference: " + array[0] + " and " + array[len - 1]); }} |
Maximum Difference is: 118 Two elements with largest difference: 2 and 120
- Time Complexity: O(n)
- Auxiliary Space: O(1)
Note: Both Minimum and Maximum element in the above code can also be determined in a single for loop by comparing every element of an array with the minValue and maxValue and update them accordingly. In this way, a single for loop can return both the minValue and maxValue, and the lines of code will be reduced.
