Given an array of integers in range 0 to N-1, find all duplicate numbers in array. Array is not sorted. For example:
A = [2,4,3,2,1,5,4] Duplicate numbers = 2,4 A = [4,1,3,2,1,1,5,5] Duplicate numbers = 1,5
Methods to find all duplicate numbers in array
Method 1 : Keeping track of visited number
Basic idea behind problem is to keep track that whether we have visited the number before or not. To keep track, we can use hash. This includes 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 given array. If the bit is set already, its an duplicate number. It takes O(n) extra space which is actually less than earlier O(n) as only bits are used.
Method 2 : Using array itself
Can we use the given array itself to keep track of visited number. How can we change a number in an array while be able to get the original number back whenever needed? It is to make number negative.
Idea is to make number at ith index of array negative whenever we see number i in 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.Implementation is given below.