Is there a linear-time algorithm to determine if an array has duplicate entries that uses only constant extra space?

Determining whether or not an array has duplicate entries has two straightforward solutions:

  • Build a hashset of entries, then search for elements in this hashset. This takes $ \mathcal O(n)$ time and $ \mathcal O(n)$ extra space.
  • Sort the array, then search for consecutive elements that are the same. This takes $ \mathcal O(n \log n)$ time and $ \mathcal O(1)$ extra space.

Is there an algorithm that can solve this problem with the best of both approaches, using only $ \mathcal O(n)$ time and $ \mathcal O(1)$ extra space?

Question Finding duplicate in immutable array in linear time and constant space is similar, but the solution to that question only works when the values come from the set $ \{1, …, n\}$ ; my values are large integers. Also unlike that question, I allow the input array to be modified and used as a workspace.

One strategy might be to attempt to turn the array into a kind of hashtable. However, this seems like it won’t work because of the lack of empty space (which makes both moving objects into place hard, as well as getting $ \mathcal O(1)$ queries.).

However, I suspect that this cannot actually be done, but I’m not sure how to go about proving it.