Why this is a hard question?

• Use HashSet, it cost O(1) space.

Then loop the numbers
If it's in the set, return that number;
else, add it into the set.

My Java code takes only 8ms to complete all the test cases.

It should be a simple question.

• HashSet cost O(n) space.

• Did you really understand this problem?
The following is the request for this Alogrithm:
Note:
You must use only constant, O(1) extra space.

• From other aspect, he may be right. Say if we create a bitmap whose length is 2^64-1(constant, O(1) space with respect to n), and use it as a hashmap...

• From mathematical perspective, the space complexity of such solution increases linearly as the length of the array grows, no matter what space unit it is - 1 bit or 8 byte.

• I think you should understand the space complex of HashSet is O(n).

• Do you think the bitmap need O(n) space? We need to represent the nums from 1 to n.Although the bit map could reduce the space we use , it remains O(n).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.