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.
I was wondering the same. This requires the array to be sorted, which obviously leads to the complexity of O(n log n). I wonder if we can solve it by using other data structures (thus increasing the space complexity)
Can't stop thinking the same. Well, actually we can sort the array in linear time using count sort (linear in terms of the range of elements in the array) and have a linear running time algorithm but it's not really elegant since we increase space complexity.
You can't achieve O(n) through bucket sort if you don't know if the input is random. In this problem it is not directly stated. If it was, bucket would seem to be a nice option indeed.
Radix works better for strings, sure longer than 10 digits. Constant factor for such sorting would be unnecessary big, make it slower than qsort.
And you have to be careful with count sort - its speed depends on range of numbers so,
instead of O(n log n) (for qsort n = 10^5) you get O(n) (where n = ai = 10^9).
And, cause
10^5 * log(10^5) < 10^9
log(10^5) < 10^4
then count works longer for big input.
Also, for input like
{0, 10^9}
count sort still needs O(10^9) time.
Yes it could be solved in O(n) time, but would require enormous space ~ an array of 2*pow(10,9) locations.
Take the input temp and store it in a location a[temp+1000000000]th location.Next iterate throough the array and find the closest occuring elements. Also, if any element occurs more than once,print 0.
To further increase the process you can take min and max values during the input of the temp. Now you would only have to iterate from min to max values present in the array. And if any element's counter crosses 1, break and output 0.
However, this would not be recommended here due to high space complexity.This has great purposes in other problems.
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!
This should do it without sorting. It is O(cn) for time and O(n) for space.
BUT, it times out on the last two input sets since the array values are very large(-10^9 < a < 10^9), while n < 10^5. This yields a constant that is larger than n.
If you have a domain with a much smaller range for a, it would make sense.
Minimum Absolute Difference in an Array
You are viewing a single comment's thread. Return to all comments →
Is it possible to solve it better than O (n log n)?
I was wondering the same. This requires the array to be sorted, which obviously leads to the complexity of O(n log n). I wonder if we can solve it by using other data structures (thus increasing the space complexity)
Can't stop thinking the same. Well, actually we can sort the array in linear time using count sort (linear in terms of the range of elements in the array) and have a linear running time algorithm but it's not really elegant since we increase space complexity.
Yeah, but space doesnt matter. Obviously we would need more space to decrease the runtime.
Can this problem be solved without ever using any sorting algm?
Well you could, by comparing each element with every other element but that'd result in O(n^2)
But that'd be like worse than O(n log n). Guess we could sort by count or radix or bucket to achieve O(n) in sorting
You can't achieve O(n) through bucket sort if you don't know if the input is random. In this problem it is not directly stated. If it was, bucket would seem to be a nice option indeed.
Radix works better for strings, sure longer than 10 digits. Constant factor for such sorting would be unnecessary big, make it slower than qsort.
And you have to be careful with count sort - its speed depends on range of numbers so, instead of O(n log n) (for qsort n = 10^5) you get O(n) (where n = ai = 10^9).
And, cause
then count works longer for big input.
Also, for input like {0, 10^9} count sort still needs O(10^9) time.
Yes it could be solved in O(n) time, but would require enormous space ~ an array of 2*pow(10,9) locations.
Take the input temp and store it in a location a[temp+1000000000]th location.Next iterate throough the array and find the closest occuring elements. Also, if any element occurs more than once,print 0.
To further increase the process you can take min and max values during the input of the temp. Now you would only have to iterate from min to max values present in the array. And if any element's counter crosses 1, break and output 0.
However, this would not be recommended here due to high space complexity.This has great purposes in other problems.
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!
This should do it without sorting. It is O(cn) for time and O(n) for space.
BUT, it times out on the last two input sets since the array values are very large(-10^9 < a < 10^9), while n < 10^5. This yields a constant that is larger than n.
If you have a domain with a much smaller range for a, it would make sense.