There is O(N*log(N)) solution with O(N) memory, and only due to sorting