Find duplicates in O(n) time and O(n) extra space.

Posted by N.K. Chauhan on Sep 18, 2022

Given an array of n elements that contains numbers from 0 to n-1, with any of these numbers appearing any number of times in any order (non-sorted).

Find these repeating numbers in O(n) time and O(n) memory space.

Return -1 if there is no duplicate.

Input: {0, 3, 1, 2}
Output: -1

Input: {2, 3, 1, 0, 3, 2, 3, 0}
Output: 3, 2, 0


Solutions

Method 1: Using an extra array of length "n"

Traverse the given array and keep track of the count of all elements in the array using a temporary array tmp[] of size n.

When you see an element whose count is already "1" print it. This specific "tmp[arr[i]] == 1" check will handle scenarios where an element occurs more than 2 times.

This method uses the range given in the question to restrict the size of tmp[].

Complexity

The time complexity of this solution is O(n) and space complexity is O(n).

Related


Word Break Problem (Using HashMap and DP)

Find a triplet in an array that sums to a given number

Print all possible permutations of an Array in O(1) space

Two Sum - return index of a pair of array elements with a given sum

Rain water trapping problem - O(n) time & O(n) space

Longest substring without repeating characters

Print all Subsets (Power Set) of a given array

Program to print Intersection of two sorted arrays

Count the number of inversions in an array - in O(n log n) time

Merge two sorted arrays in O(1) space

Program to print Union of two sorted arrays