Finding out two such elements out of an unsorted array which have minimum difference without sorting the array

Question

We have been given an array of integer :

45, 10, 56, 42, 95, 78.

We have to find the two elements which have the minimum difference. I did that in linear time complexity but it works only on the sorted order which altogether leads the running time in quadratic complexity. Do we have any approach where we can do it in logarithmic or linear time complexity?

Thanks in advance.

Answer 1

Just sort the array with Heapsort which always is in O( n * log n). After that you apply your algorithm which is, as you told, in O(n). So you will have n + n * log n which is still in O(n * log n)