Tags: , ,

# Find all duplicate numbers in array

Given an array of positive integers in range 0 to N-1, find all duplicate numbers in the array. The array is not sorted. For example:
A = [2,4,3,2,1,5,4] Duplicate numbers are 2,4 whereas in A = [4,1,3,2,1,1,5,5] duplicate numbers are 1,5.

Brute force solution would be to keep track of every number which is already visited. The basic idea behind the solution is to keep track that whether we have visited the number before or not. Which data structure is good for quick lookups like this? Of course a map or hash.
The time complexity of this solution is `O(n)` but it has an additional space complexity of `O(n)`.

To reduce space requirement, a bit array can be used, where ith index is set whenever we encounter number i in the given array. If the bit is set already, its a duplicate number. It takes `O(n)` extra space which is actually less than earlier `O(n)` as only bits are used. The time complexity remains `O(n)`

## Find duplicate numbers in an array without additional space

Can we use the given array itself to keep track of the already visited numbers? How can we change a number in an array while also be able to get the original number back whenever needed? That is where reading the problem statement carefully comes. Since array contains only positive numbers, we can negate the number at the index equal to the number visited. If ever find a number at any index negative, that means we have seen that number earlier as well and hence should be a duplicate.

Idea is to make the number at ith index of array negative whenever we see number i in the array. If the number at ith index is already negative, it means we have already visited this number and it is duplicate. Limitation of this method is that it will not work for negative numbers.

### Duplicate numbers implementation

```package AlgorithmsAndMe;

import java.util.HashSet;
import java.util.Set;

public class DuplicatesInArray {

public Set<Integer> getAllDuplicates(int[] a )
throws IllegalArgumentException {

Set<Integer> result = new HashSet<>();

if(a == null) return result;

for(int i=0; i<a.length; i++) {
//In case input is wrong
if(Math.abs(a[i]) >= a.length ){
throw new IllegalArgumentException();
}

if (a[Math.abs(a[i])] < 0) {
} else {
a[Math.abs(a[i])] = -a[Math.abs(a[i])];
}
}
return result;
}
}

```

Test cases

```package Test;

import AlgorithmsAndMe.DuplicatesInArray;
import java.util.Set;

public class DuplicatesInArrayTest {

DuplicatesInArray duplicatesInArray = new DuplicatesInArray();

@org.junit.Test
public void testDuplicatesInArray() {
int [] a = { 1,2,3,4,2,5,4,3,3};
Set<Integer> result = duplicatesInArray.getAllDuplicates(a);

result.forEach(s -> System.out.println(s));
}

@org.junit.Test
public void testDuplicatesInArrayWithNullArray() {
Set<Integer> result = duplicatesInArray.getAllDuplicates(null);

result.forEach(s -> System.out.println(s));
}

//This case should generate an exception as 3 is greater than the size.
@org.junit.Test
public void testDuplicatesInArrayWithNullArray() {
int [] a = { 1,2,3};
try{
Set<Integer> result = duplicatesInArray.getAllDuplicates(a);
} catch (IllegalArgumentException  e){
System.out.println("invalid input provided");
}
}
}

```

The complexity of the algorithm to find duplicate elements in an array is `O(n)`.