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

This video is contributed by Harshit Jain.

[shaunsawyer]

Should be changed from 0..n-1 to 1..n-1 as I don't think 0 will work. If 0 occurs at index i and the number i is duplicated in the array we won't be able to mark it as negative.

[hermesmercuriustrismegistu]

Amazing! Nice neat efficient solution but how would someone come on fly with such a solution in an interview especially under stress???!! Coming with such a solution is a marathon!

[dba]

This program has a serious bug - it accesses array out of bounds. Here: arr[abs(arr[i])]
Try with large enough numbers enough times, and it will cause seg fault.

[namanaggarwal]

This approach will not work if duplicates' frequency >=3 .. In that case same elements will be printed twice or as many times as their (frequency-1)
Thus we wont be able to print uniquely duplicate elements

[gauravsonkusle]

Better approach in the article:- First a[ a[i]%n ] = a[ a[i]%n ] + n; then, a[i] is repeated element if a[i]%n >= 2; n is len(a)

[gurjarc]

Wondering where in real world, we need to solve this problem with this constraint?
The constraint of the input to contain only elements from 0 to n-1, where n is the length of the array is not what you would encounter in real world

[kaifahmad]

Yet another great problem Explained fabulously.

[Rafayak]

very nice! Regurgitated the slides without explaining the algo,

[tincustefanlucian]

The title is misleading because it's a generic affirmation which is expected to work in all cases but it's not. It's like saying pigs can fly! Yeah only pigs in planes fly or with some device attached because the plane flies or the other device flies.

Back to the problem: It works only for some very specific arrays which don't have elements bigger than the size of array and no negative numbers and the array is corrupted at the end so finally it's O(n) space. Also if the array starts with 0, 0, .... it cannot detect double 0.

[mohammedjulfikaralimahbub]

Apart from various issues mentioned in the comment among which most of the issues are valid but my question is how will you handle an array having both -1 and 0 repeated as increment by +1 will make -1 as 0 ...

[xinweixiong]

The first note of that question: You must not modify the array (assume the array is read only).

[daixtr]

Given arr = {1, 2, 3}; is an invalid input because it contains the element 3. You said, 0 to n-1 only therefore the value of 3 is illegal. You cannot also allow element of 0 because you cannot negate it. So this algo assumes that at least there is a repeating element to satisfy the constraint. For example, arr = {1, 2, 1}; is valid input. So many constraint, and a-priori requirements. But the curious funny part is that the pre-condition that at least one element must repeat to make the input valid is also the problem that the algo is meant to determine.

[konstantingeist]

It wasn't stated input parameters can be modified. Bad solution in 2017 when we want to make everything we can const for better parallelization. This is probably something from the 1970's.

[mukundpatel]

I have some idea to manage Occurrence also if we make it float
arr = {1, 2, 3, 1, 6, 6};
// add .1 at arr[ arr[i]]

for i 0 to length
arr[ arr[i] ] += 0.1;

Occurrence of any element will be at arr[ element], before the decimal point

[gauravghosh]

great solution. I had a doubt:what if an element is repeated 4 times then it's index will be negative and we will insert that index twice in our ans.

[gurjarc]

Is modifying the content of the array not equal to using extra Space?
Think about it. The method calling the RemoveDuplicates method can no longer use the array as it is corrupted.. So in the real world, it amounts to doing it with O(n) space as the calling method has to create a duplicate array and pass it on..., even though not obvious at first.

[meghanavaitla]

what if we have -1 and 0 if we increment all elements by 1 then -1 becomes 0

[sharanpai]

What if a[i] is greater than length of the array

[pratyushpare]

Apart from this question is there any solution which can handle duplicacy of both +ive and -ive number with same complexity and if not tnen what will be the best suitable method for this problem ?

[tusharupadhyay]

What if all elements in array are greater than its index value