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 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.
|
Iteration
|
Array
|
||||||||||||||||||||||
|
1
|
|
||||||||||||||||||||||
|
2
|
|
||||||||||||||||||||||
|
3
|
|
||||||||||||||||||||||
|
4
|
|
||||||||||||||||||||||
|
5
|
|
In this example the range is [1,10]
Since the array values are in the range [1,N] and the array stores the values from [0,N-1] we are using index-1 to locate the element to be negated.
In the first iteration value is 5, array[4] is negated.
In the second iteration value is 1, array[0] is negated
In the third iteration value is 3, array[2] is negated
In the fourth iteration value is 2, array[1] is negated
In the fifth iteration value is 1 again, We are supposed to make array[0] negative, but we found that it is already negative. Hence we can conclude that it has duplicates.
Here is the Java Implementation.
/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/13/13
* Time: 11:48 PM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
int[] array1 = {5,1,3,2,10,4,6,8,9,7};
if( hasDuplicates(array1) )
System.out.println("Array has duplicates");
else
System.out.println("Array does not have duplicates");
int[] array2 = {5,1,3,2,1,4,6,8,4,7};
if( hasDuplicates(array1) )
System.out.println("Array has duplicates");
else
System.out.println("Array does not have duplicates");
}
public static boolean hasDuplicates(int[] array)
{
for(int i = 0; i < array.length; i++ )
{
//take the absolute value because it might have been negated by some previous
//operation
int index = Math.abs( array[i] ) - 1;
//If array[index] is negative; we have a duplicate, return true
if( array[index] < 0 )
return true;
else // array[i] is found first time, negate array[ array[i] ]
array[index] = -array[index];
}
return false;
}
}