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.
min_abs = min((abs(arr[i] - arr[i-1]) for i in range(1, len(arr))))
s = set()
for x in arr:
if x in s:
for d in range(1, min_abs):
if x + d in s or x - d in s:
min_abs = d