I was recently solving a problem. The problem simply asks the following, given a list of integers in range 1 to n, find the first duplicate value in the list,

now the obvious solution is to use a hash table and do it in O(n) space and O(n) time, but I found out there is a neat trick which we can use to solve it in O(1) space.

We can just iterate the array, and then for a[i], we mark the index a[a[i]] as negative, and then we just check if we have made any integer negative before, if yes, that is the first duplicate value.

My question is, what if we have negative values as well in the array? Is there a general approach to solve this?

CodePudding user response：

Storing the array itself is O(n) space complexity. If you care about additional space used, all you are doing is using negative values as a flag of 1 bit of storage, which reduces the range of values you can store by 1 bit. You can come up with any number of schemes to store an extra flag bit somewhere: for example, handling values between around int_min/2 and int_max/2, you could shift all values up to be non-negative then use the sign bit, but it is not worth it in practical applications unless you are severely memory constrained. For truly big-data operations, where you cannot even store the whole array, you can use probabilistic online methods like count-min sketch.

CodePudding user response：

what if we have negative values as well in the array?

If you mean that values are in the range −