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

Objective: Given an array of integers, find out duplicates in it.


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



Naive approach: Use 2 loops. Check each element in the array with all other elements in the array and check if it has the same value.

Time Complexity : O(n^2) Space Complexity: O(1)



Sorting approach: Sort the array, this will bring all the duplicates together if present. Now navigate the array and check the adjacent elements to check for duplicates.

Time Complexity : O(nlogn) Space Complexity: O(n) by using merge sort.



Better Solution : Use Hash map. Store the count of each element of array in a hash table and later check in Hash table if any element has count more than 1. ( Similar approach is used in problem – Find the first non repeating character in a given string

Time Complexity : O(n) and Space Complexity: O(n).



Better Solution (Conditional) : O(n) time and O(1) extra space.

  • This solution works only if array has positive integers and all the elements 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.


  • The code given below does not handle the case when 0 is present in the array.
  • To handle 0 in array, while navigating the array, when 0 is encountered, replace it with INT_MIN and if INT_MIN is encountered while traversing, this means 0 is repeated in the array.

Similar approach used in problem : If array has all consecutive numbers.



Array has duplicates : 3
Array has duplicates : 2

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: