Finding duplicates in an array using negation, single scan -O(n)

If the array elements are positive numbers and also elements are in the range 0 to n-1 , then we can find duplicate elements using negation technique. For each element a[i], go to the array element whose index is a[i], that means we select a[a[i]] and mark this value as -a[a[i]]. That is we negate the value of a[a[i]. Continue this process until we find the element that is already negated.

Note:

  1. The solution does not work if the given array is read only, that means no manipulation is allowed to array elements.
  2. The solution will work only if the array elements are positive and are in the range 0 to n-1.

Finding duplicates in an array using negation – O(n)

Sample Test Client for above program

Leave a Comment