Be the first user to complete this post

Add to List 
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.
Example:
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 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)
Code:
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.
Code:
Better Solution : Use Hash map. Store the count of each element of array in a hash table and later check in the 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).
Code:
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 n1 where n is the size of the array.
 Navigate the array.
 Update the array as for ith index : arrA[arrA[i]] = arrA[arrA[i]]*1 (if it already not negative).
 If is already negative, we have duplicates, return false.
Note:
 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.
Code:
Output:
Array has duplicates : 3 Array has duplicates : 2
Also Read: