Make delicious recipes!

Find 2 elements with maximum difference in an array

Problem: Given an unsorted array, find two elements a[i] and a[j] such that i < j and difference between a[i] and a[j] is maximum in the array.

For example, in the following array [30, 12, 15, 22, 25, 7, 18], the elements with maximum difference are 12 and 25

Note that neither 12 nor 25 are the maximum or the minimum of the array and yet they have the maximum difference.

A naive solution would be O(n2) where we run 2 loops, comparing each element with all the other elements, finding the difference and then choosing the maximum out of it.

A tricky solution is as follows:

1) If 2 elements have the maximum difference, then those 2 elements must be the maximum and minimum among the elements between those 2 elements. There may be other maximum/minimum elements outside the elements between these 2 elements.

2) Keep track of the minimum elements found so far and the maximum difference found so far with that element. If a new minimum is found lower than current minimum, then we will need a new difference to beat the current difference. But that new difference will clearly use the new minimum element. This implies that older minimum continues to be in the solution until a greater difference is found with the new minimum.

With the above considerations, following O(n) solution can be coded:

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal