Identifying two such elements from an unsorted array that have minimal difference without sorting the array
We are given an array of integers:
45, 10, 56, 42, 95, 78.
We need to find two elements that have the smallest difference. I did it in linear time complexity, but it only works on sorted order, which generally results in a quadratic runtime. Do we have any approach where we can do this in logarithmic or linear time complexity?
Thanks in advance.
+3
abhi
source
to share
1 answer
Just sort the array with Heapsort, which is always in O( n * log n)
. After that, you apply your algorithm, which you said in O(n)
. This way you will n + n * log n
have which is still inO(n * log n)
+1
Rafael Regh
source
to share