Clever Geek Handbook

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


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


source






More articles:


All Articles