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

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.

Thank You So Much ..................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

😍😍😍😍😍😍😍😍

Thank you so much

thanks!

Plz add english subtitles in ur videos..cz sometimes voice not clear this will help me a lot If you add English subtitle in your video

Yet another great problem Explained fabulously.

vector<int> duplicates(int arr[], int n)
{
map<int,int>mp;
vector<int>v;
int c = 1;
for(int i = 0; i < n; i++)
{
int ind = arr[i] % n;
arr[ind] += n;

if(arr[ind]/n == 2)
{
v.push_back(ind);
c = 0;

}
}
sort(v.begin(),v.end());

if(c)
{
v.push_back(-1);
return v;
}
else
{
return v;
}
}

The solution is good but the way you explain is so bad. Might as well just post the solution and get it over with.

Edit:- Just checked its a wrong solution. Doesn't work for
int arr[] = {2, 2, 0}

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

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)

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

Buffer overflow / segfault may occur.

Geeks for geeks solution vjdeo sucks...

This won't work all cases, the efficient I could write with the time of O(n) => one-time traverse through the array
```
def find_duplicates(nums)
tracker = {}
result = []
nums.each do |n|
if tracker[n]
result << n
else
tracker[n] = true
end
end
result
end
```

wont work if array is constant

What if the array is read only?

can we don something like this if numbers beyond n - 1 present in array

I think Nick White had a video on this.

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!

create a map of occurrence of the elements in the array and then if their occurrence value is greater than one push them in the resultant array. time complexity O(n)

this is not algorithm but shit. It wont work for 0. It wont work for anything that is greater than size of array. And the title is Find duplicates in O(n) time and O(1) extra space. I think I should never go to geeksforgeeks. At least they should validate the algorithm on real case situation.

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.

There should be a pre condition : all element's value is less than n-1

wrong

thanks pajeet!

plz hlep

an alien needs to enter the password to board the spaceship can you help him recall the 4 digits code with non-repeated digits using these clues.
1.The third digit is the smallest prime number.
2.The fourth digit is the product of the secound and third numbers.
3.The first digit is the difference between the fourth and third digits.
4.only one the digit is an odd number.
5. None of the digits are greater than 8.

This algo is failing for a simple scenario where, there is no duplicates, it still shows repeating element, like if we call the method on array {1,2,3} it will print 3 as a repeating element while its not.

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

what will happen when [10,10,10]

wrong solution

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

MEMORY VIOLATION
check if the array as following Arr = [2^31, 1, 2, 1]
it needs to access Arr[2^31] !!
which is not allowed if the memory protection unit is enabled in the compiler

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

very nice! Regurgitated the slides without explaining the algo,

It should be A[abs(A[i])-1] and not A[abs(A[i])] . Array out of bounds error !. But great explanation. Thanks !

its not working number 1,2,3,1,6,6,49,49...dumb ass code

Given an array (Dimension 6), check if array doesn’t have duplicates, and how many duplicates are there
plsssssssssssssss

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 ?

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 ...

what if arr[]={1,2,3,1,3,3,1,6,6} ??
Actually this code will print the duplicates no. more than 1,which should not be the output.

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.

This code is wrong. It has dead lock in it.

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.

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

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.

If an element is repeating n times, this solution will print it n-1 times.

Super clever! Thank you!

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.