You are viewing a single comment's thread. Return to all comments →
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.
def minimumAbsoluteDifference2(n, arr):
min_abs = abs(arr - arr)
s = set(arr[:2])
for x in arr[2:]:
for d in range(1, min_abs):
if x + d in s or x - d in s:
min_abs = d