That problem is a terrible interview question, mainly because it's completely trivial with O(n) memory (just use a Set), but requires a different branch of comp sci at O(1).

Personally I also feel that any question that needs an O(1) memory when you _start with an array_ is disingenuous. O(1) memory was used for things like tape storage, where N was some huge external storage. If you already have an array, then the chance you don't have double that memory are dibcus.