Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

You may also like...