Codility AbsDistinct: Why is this solution not O(n)?
I don't see any reason why your solution would not be O(N).

However, it would fail if the array contained Integer.MIN_VALUE, since its absolute value won't fit within an int.