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:
|
