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.
This is O(n) without sorting. It is O(cn) for time and O(n) for space, where
c <= max(arr) - min(arr)
BUT, it times out on the last two input sets since the range of values is very large(-10^9 < a < 10^9), while n < 10^5. This yields a constant c that is larger than n, so it's slower than O(n^2) for those inputs.
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 →
This is O(n) without sorting. It is O(cn) for time and O(n) for space, where c <= max(arr) - min(arr)
BUT, it times out on the last two input sets since the range of values is very large(-10^9 < a < 10^9), while n < 10^5. This yields a constant c that is larger than n, so it's slower than O(n^2) for those inputs.
If you have a domain with a much smaller range for a, it would make sense.