# Find duplicates in an given array in O(n) time and O(1) extra space.

Objec­tive: Given an array of inte­gers, find out dupli­cates in it.

Exam­ple:

```int [] a = {4, 6, 2, 1, 2, 5};
Output: Array has duplicates : 2

int a [] = {1, 6, 5, 2, 3, 3, 2};
Output: Array has duplicates : 2 , 3
```

Approach:

Naive approach: Use 2 loops. Check each ele­ment in the array with all other ele­ments in the array and check if it has the same value.

Time Com­plex­ity : O(n^2) Space Com­plex­ity: O(1)

Code:

Sort­ing approach: Sort the array, this will bring all the dupli­cates together if present. Now nav­i­gate the array and check the adja­cent ele­ments to check for duplicates.

Time Com­plex­ity : O(nlogn) Space Com­plex­ity: O(n) by using merge sort.

Code:

Bet­ter Solu­tion : Use Hash map. Store the count of each ele­ment of array in a hash table and later check in Hash table if any ele­ment has count more than 1. ( Sim­i­lar approach is used in prob­lem — Find the first non repeat­ing char­ac­ter in a given string

Time Com­plex­ity : O(n) and Space Com­plex­ity: O(n).

Code:

Bet­ter Solu­tion (Con­di­tional) : O(n) time and O(1) extra space.

• This solu­tion works only if array has pos­i­tive inte­gers and all the ele­ments in the array are in range from 0 to n-1 where n is the size of the array.
• Nav­i­gate the array.
• Update the array as for ith index :- arrA[arrA[i]] = arrA[arrA[i]]*-1 (if it already not negative).
• If is already neg­a­tive, we have dupli­cates, return false.

Note:

• The code given below does not han­dle the case when 0 is present in the array.
• To han­dle 0 in array, while nav­i­gat­ing the array, when 0 is encoun­tered, replace it with INT_MIN and if INT_MIN is encoun­tered while tra­vers­ing, this means 0 is repeated in the array.

Sim­i­lar approach used in prob­lem : If array has all con­sec­u­tive numbers.

Code:

Out­put:

```Array has duplicates : 3
Array has duplicates : 2
```