Given an array of integers, find Maximum difference between two elements such that larger number appears after the smaller number. In this tutorial, I am going to discuss multiple approaches and their java code to find maximum difference between two elements.
For example :
Example 1:
arr = {2, 5, 15, 6, 4}
Output: 13
The difference between 15 and 2 is 13. Element 15 is greater than 2 and it satisfies our condition that larger number appears after the smaller number.
Example 2:
arr = {7, 9, 5, 6, 13, 2};
Output : 8
The difference between 13 and 5 is 8 (13-5).
I have also mentioned the video tutorial link at the end of this post.
Find Maximum Difference between Two Elements of an Array
METHOD 1: Using two for loops
In this approach, we are going to use two for loops to solve this problem. The time complexity of this approach is O(n2).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
/* Java Program to Find Maximum Difference between Two Elements of an array using brute force approach */ public class MaxDifference { public static int bruteForce(int[] arr) { int max = 0; //Using two for loops for (int i = 0; i < arr.length; i++) { for(int j = i+1; j < arr.length; j++) { /* This condition ensure that the larger element appears after the smaller element */ if(arr[i] < arr[j]) { //Find max max = Math.max(max, arr[j] - arr[i]); } } } return max; } public static void main(String[] args) { int arr[] = {2, 5, 15, 6, 4, 8, 9}; //Method call int result = bruteForce(arr); System.out.println(result); } } |
The time complexity of method 1 is O(n2). Can we do better than that? Yes we can solve this problem in O(n) time complexity.
Find common element in three sorted array
Find common elements in two arrays
Find Maximum Difference between Two Elements of an Array : Java Code
In this approach, instead of taking difference of the picked element with every other element, we can take the difference with the minimum element found so far. So we need to keep track of two things:
1) Maximum difference found so far.
2) Minimum number visited so far.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
/* Find Maximum Difference between Two Elements of an Array in O(n) Time Complexity. */ public class MaxDifference { public static int findMaxDiff(int arr[]) { int maxDiff = arr[1] - arr[0]; int minEle = arr[0]; for(int i = 1; i < arr.length; i++) { if((arr[i] - minEle) > maxDiff) { maxDiff = arr[i] - minEle; } if(arr[i] < minEle) { minEle = arr[i]; } } return maxDiff; } public static void main(String[] args) { int arr[] = {2, 5, 15, 6, 4, 8, 9}; int result = findMaxDiff(arr); System.out.println(result); } } |
