Problem solving with programming: Checking duplicates in an array in O(n) time and O(1) space

Problem solving with programming: Checking duplicates in an array in O(n) time and O(1) space

Let us consider an array of size N contains numbers in the range [1,N]. We have to find if it has duplicates in linear time - O(n) and by using only constant extra space - O(1). 

Let us also have a restriction that we should traverse the array only once. Take a look at the following algorithm.

When traversing through the elements of the array, we consider each element as an index into the same array and negate the value at that index. If we already find a negative value at this index (i.e we have already seen this element), we can say that the array has duplicates.

Let us see understand this algorithm with a small example. The following table gives a snapshot of the array in each iteration.

Read full article from Problem solving with programming: Checking duplicates in an array in O(n) time and O(1) space