We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
You could do an O(n) check to see if the range of the numbers was sufficiently small to make it possible for this to be better than using sorting. If you knew the differences of the numbers had a common factor, you could use this to shrink the range, but finding the GCD of two integers is probably O(log(max(abs(n1), abs(n2)))), so this only helps without additional information when the range of the integers is small compared to their number. In this situation (n values from m possibilities where m < n), the pigeon hole principle tells us immediately (O(1)) that the min distance is zero!
Minimum Absolute Difference in an Array
You are viewing a single comment's thread. Return to all comments →
You could do an O(n) check to see if the range of the numbers was sufficiently small to make it possible for this to be better than using sorting. If you knew the differences of the numbers had a common factor, you could use this to shrink the range, but finding the GCD of two integers is probably O(log(max(abs(n1), abs(n2)))), so this only helps without additional information when the range of the integers is small compared to their number. In this situation (n values from m possibilities where m < n), the pigeon hole principle tells us immediately (O(1)) that the min distance is zero!