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

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

Given an array of n elements that contains numbers from 1 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 using only constant memory space, O(1).

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


Solutions

Method 1: Marking elements (-)ve

The idea is to iterate the array from 0 to n-1 and mark the arr[i]th element as -ve, if arr[i]th element is -ve print arr[i].

The below code doesn't work if "0" is present in the array.

It will not work if the array contains more than 2 duplicates of an element. For example: {1, 2, 3, 1, 1, 3, 4} it will give output as : 1 1 3.

This more than 2 duplicates issue can be resolved by iterating the array twice. In the first iteration, mark the element -ve only if it is positive, and in the second iteration, print the index of -ve elements.

Complexity

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

Method 2: Adding "n" and using modulus "n"

This solution works for "0" as an element and also handles scenarios when there are more than two duplicates of an element present in the array.

The idea is to iterate the array from 0 to n-1 and add "n" to the element at the arr[i]th index.

If any element "e" occurs more than once, the "eth" index will have a value greater than or equal to 2 * n.

Iterate the array a second time and print the "index" of elements having a value greater than or equal to 2 * n.

In this solution, only one thing is left to be taken care of. As we are adding n to array elements, this will cause an "ArrayIndexOutOfBoundsException" while trying to get "arr[arr[i]]" because arr[i] is also acting as an index and the value will be out of the n-1 range. (n is added to the element at arr[i] for every occurance of "i").

To overcome this, the only change needed is to get "arr[i] % n" instead of "arr[i]" - so for an array of length n = 4, if element "3" is present twice and 2 is present at index 3, the element at index 3 will be converted to 2+4=6 and 2+4+4=10.

Now using "%", we can get 6%4 = 2 and 10%4 = 2 (no "ArrayIndexOutOfBoundsException").

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

Related


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

Program to print Intersection of two sorted arrays

Word Break Problem (Using HashMap and DP)

Longest substring without repeating characters

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

Print all Subsets (Power Set) of a given array

Program to print Union of two sorted arrays

Merge two sorted arrays in O(1) space

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

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

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