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

by

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)

/**
 * <p>Check Duplicates in the array using Math abs</p>
 * Time Complexity   ::O(n)
 * Space Complexity  ::O(1)
 * @param a
 * @return
 */
public static int checkDuplicatesWithMathAbs(int[] a){
int n=a.length;
for(int i=0;i<n;i++){
	if(a[Math.abs(a[i])]<0)
	   return a[i];
	else
	   a[a[i]]=-a[a[i]];
 }
return -1;
}

Sample Test Client for above program

public static void main(String[] args) {

/**
 * Checking duplicates in the array by placing negative values
 * Array elements should be in the range 0 to n-1
 * This solution does not work if the given array is read only and all the  * elements should be +ve
 * Time Complexity  :: O(n)
 * Space Complexity :: O(1)
 */
  int[] arr5={0,1,2,2,4,5,6};
  System.out.println(checkDuplicatesWithMathAbs(arr5));
}

Leave a Comment