Minimum Absolute Difference in an Array

  • + 0 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!