I came across this problem and I could solve this problem in O(N) time and O(N) extra space.
Here is my solution.
I am just curious to know whether this problem could be solved without extra space or not.