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.
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!
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.
well said , this algorithm is not efficient. The most safe way to identify the duplicates is sort and then match with each neightbour and compare for difference and hence seperate them into distinct ones and non distinct ones. Although this algorithm looks optimal it wont work on a real world data set. It will only work on those arrays where all numbers are + ve and each one is less than the SIZE of the array itself in this case 7 [ and each numeber is less than 7 ]
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
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
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.
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.
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.
I must agree that this is a pathetic explanation.. look at how he says - "if it is negative , we 'assume' that the element is repeated?" 'assume.' ? LOL.. You need to explain how that value being negative means an element is repeated and the rationale behind taking the absolute value...I understood it but not from this video..I went through it with pen and paper .
Much better here - ua-cam.com/video/GeHOlt_QYz8/v-deo.html This guy does not simply regurgitate solution like geeks..Teaches how he approaches the problem...explains the train of thought behind the solution and why it works... Follow this channel bro-byte by byte. To watch how brilliantly he explains , watch Knapsack and coin change videos by him. Starts from a blank page and beautifully constructs the solution.
All the people here! Geeks for Geeks do not owe you anything. It is a free video explaining a common interview question with a beautiful way. I understood it quite quickly! If you can not understand it that means you need more exposure with programming and problem solving! God help up with the cheap people! It is a free video and the lovely folks in Geeks for Geeks thankfully took the time to create and edit a video and write a complete post explaining the problem and the solution and yet we find cheap people like the ones who put this comment not happy about it!
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 ...
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
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.
In this problem, traversing the array and convert the negative integers to positive integers can get the original input array instead of creating a duplicate array. Again, Thinking in the real world sense is always good to have👍
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.
Formally your solution use O(N) of space, not O(1) - you use N sign bits in your array. If it will be array of unsigned integers, or numbers can be less than 1 - this algorithm will not work. It's possible to solve it with O(N) of space and O(N) of time, or O(1) of space and O(N log N) of time. Always tradeoff...
Maybe some programming languages really don't reserve memory for unused bits of primitive values. But in most programming languages primitive values reserve fixed amount of memory, no matter what the value is. For example in Java integer will always take 32 bits of memory, no matter whether it is 1 or 2^31.
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.
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
Arguably you are using n sign bits, so I'm not sure you can call this an O(1) space solution. As an example imagine tackling this problem for 8 bit numbers, stored in a list of 256 numbers.
In most of the programming languages primitive values take fixed amount of memory, no matter what the value is. 1 and 2^31 take the same amount of memory.
I think even if we added the '-1' it's still wrong check if the array as following Arr = [10000000, 1, 2, 1] it needs to access Arr[9999999] !! which is not allowed if the memory protection unit is enabled in the compiler
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)
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 ?
its not working and give run time error i write this code int main() { int arr[]={1,2,3,1,6,6}; int i=0; for(i=0;i=0) arr[abs(arr[i])]=-arr[abs(arr[i])]; else printf(" %d",abs(arr[i])); } } what wrong in this pls try this and give me the solution .....
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 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}
How would that work when you have integers value in Array more than the size of array . Say supposedly you have 20,30,90,80,25 .How would this logic work ??????
Deepak Joshi lets say we have the value x in an array. when we visit the element at index x and observe that it positive, we make it negative. now when theres another x in the array, it will refer to the same element at index x (which was made negative beforehand) and thus it will signify that there are two values of x in ths array (repeated values)
@@tanchienhao Yes..I understood it with pen and paper... but that was not explained at all in the video. This is the problem with many channels...I find 'byte by byte' channel to be a a rare exception though. He explains the train of thought and arrives at the solution later...does n't simply regurgitate the solution straightaway without ever explaining how you got it or why it works ..like this channel ...
To calculate "Space Complexity", you actually need to look at the extra space used by your algorithm. Also, how is it related to the input. Refer this: www.geeksforgeeks.org/g-fact-86/ for more information.
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.
for algo to work with 0...inc every element by 1 and while printing decrement it by 1..its already mentioned in the quest that its valid from 0 to n-1....although every algo has pros and cons.........its simply teaches how to think in different directions and wat diff logics can be applied to problems.
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.
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)
hey can you explain me this approch? I have been thinking about your this comment for a while now, can't understand it :(
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!
This doesn’t come by intuition. U need to practice a lot and learn solutions to problems like these type as much possible
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.
well said , this algorithm is not efficient. The most safe way to identify the duplicates is sort and then match with each neightbour and compare for difference and hence seperate them into distinct ones and non distinct ones.
Although this algorithm looks optimal it wont work on a real world data set. It will only work on those arrays where all numbers are + ve and each one is less than the SIZE of the array itself in this case 7 [ and each numeber is
less than 7 ]
The input numbers will be in the range [0, n-1]. This is clearly mentioned. So there is no possibility of seg fault.
this algorithm won't work if there are two 0s, example [0, 0, 2, 4, 3];
Given an array of n elements which contains elements from 0 to n-1 is the problem statement
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
use sets to store values
@@viditrastogi79 it will violate space complexity
use sorting then
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
Yet another great problem Explained fabulously.
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.
vector duplicates(int arr[], int n)
{
mapmp;
vectorv;
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 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.
kindly read problem statement.
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.
The first note of that question: You must not modify the array (assume the array is read only).
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.
very nice! Regurgitated the slides without explaining the algo,
I must agree that this is a pathetic explanation.. look at how he says - "if it is negative , we 'assume' that the element is repeated?" 'assume.' ? LOL.. You need to explain how that value being negative means an element is repeated and the rationale behind taking the absolute value...I understood it but not from this video..I went through it with pen and paper .
Much better here - ua-cam.com/video/GeHOlt_QYz8/v-deo.html
This guy does not simply regurgitate solution like geeks..Teaches how he approaches the problem...explains the train of thought behind the solution and why it works...
Follow this channel bro-byte by byte. To watch how brilliantly he explains , watch Knapsack and coin change videos by him. Starts from a blank page and beautifully constructs the solution.
All the people here! Geeks for Geeks do not owe you anything. It is a free video explaining a common interview question with a beautiful way. I understood it quite quickly! If you can not understand it that means you need more exposure with programming and problem solving! God help up with the cheap people! It is a free video and the lovely folks in Geeks for Geeks thankfully took the time to create and edit a video and write a complete post explaining the problem and the solution and yet we find cheap people like the ones who put this comment not happy about it!
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 ...
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
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
What if a[i] is greater than length of the array
What if the array is read only?
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.
In this problem, traversing the array and convert the negative integers to positive integers can get the original input array instead of creating a duplicate array.
Again, Thinking in the real world sense is always good to have👍
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.
Formally your solution use O(N) of space, not O(1) - you use N sign bits in your array.
If it will be array of unsigned integers, or numbers can be less than 1 - this algorithm will not work.
It's possible to solve it with O(N) of space and O(N) of time, or O(1) of space and O(N log N) of time. Always tradeoff...
he is not creating new array dude !
But he use "unused" sign bits, so _formally_ he use array of bits with size of N
Maybe some programming languages really don't reserve memory for unused bits of primitive values. But in most programming languages primitive values reserve fixed amount of memory, no matter what the value is. For example in Java integer will always take 32 bits of memory, no matter whether it is 1 or 2^31.
Thank You So Much ..................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Buffer overflow / segfault may occur.
what if we have -1 and 0 if we increment all elements by 1 then -1 becomes 0
@Meghana elements are compulsory in the range of *0 to n-1* .
I think Nick White had a video on this.
Given an array (Dimension 6), check if array doesn’t have duplicates, and how many duplicates are there
plsssssssssssssss
Thank you so much
can we don something like this if numbers beyond n - 1 present in array
What if all elements in array are greater than its index value
Read the problem statement again
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.
The test case is wrong for this question. There are n+1 numbers inside array of length n. So there will always be a duplicate present inside.
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
Arguably you are using n sign bits, so I'm not sure you can call this an O(1) space solution. As an example imagine tackling this problem for 8 bit numbers, stored in a list of 256 numbers.
In most of the programming languages primitive values take fixed amount of memory, no matter what the value is. 1 and 2^31 take the same amount of memory.
It should be A[abs(A[i])-1] and not A[abs(A[i])] . Array out of bounds error !. But great explanation. Thanks !
I think even if we added the '-1' it's still wrong
check if the array as following Arr = [10000000, 1, 2, 1]
it needs to access Arr[9999999] !!
which is not allowed if the memory protection unit is enabled in the compiler
wont work if array is constant
wrong solution
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)
plz read the quest carefully...its written O(1) space
This code is wrong. It has dead lock in it.
If an element is repeating n times, this solution will print it n-1 times.
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 ?
sort the array than check for previous element in array, if same then print
there is 1 more solution but its good too.
thanks!
its not working and give run time error i write this code
int main()
{
int arr[]={1,2,3,1,6,6};
int i=0;
for(i=0;i=0)
arr[abs(arr[i])]=-arr[abs(arr[i])];
else
printf("
%d",abs(arr[i]));
}
}
what wrong in this pls try this and give me the solution .....
I ran it on our online compiler: code.geeksforgeeks.org/YRCZgT
And, it did not give any error.
brother its giving output only 1,not 1,6 pls try it and give me solution....
The array is of size 6. so you can not give 6 as element of array. Highest is 5 i.e. (n-1)
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
Question says given an array of size N containing elements from 0 to N-1...
wrong
I think this won't work for negative numbers in an array!!
Please read the question - It clearly says the numbers are from 0 to n-1 where
n is the number of elements in the array.
Thank you for the clarification, Malhar.
this solution cannot handle negative no and out of bound nos
best solution is to use sorting
1) sort array
2) check for next element is same
read the Q carefully
There is a requirement to implement this in O(n) time. Sorting will give you O(n log n) at best.
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 would happen if the number inside the arrays is bigger than the array size. For example int arr[] = {9,9,1};
Then this algorithm will not work. This program will work only for the arrays with the numbers in range [0, n-1]
How would that work when you have integers value in Array more than the size of array . Say supposedly you have 20,30,90,80,25 .How would this logic work ??????
what will happen when [10,10,10]
such an array is not possible..It is given that when size=n, numbers from 0 to n-1 are present in the array..some of them are repeating..
Can someone explain why this logic works?
Deepak Joshi lets say we have the value x in an array. when we visit the element at index x and observe that it positive, we make it negative. now when theres another x in the array, it will refer to the same element at index x (which was made negative beforehand) and thus it will signify that there are two values of x in ths array (repeated values)
man ur explanation is gold ! thanks
@@tanchienhao Yes..I understood it with pen and paper... but that was not explained at all in the video. This is the problem with many channels...I find 'byte by byte' channel to be a a rare exception though. He explains the train of thought and arrives at the solution later...does n't simply regurgitate the solution straightaway without ever explaining how you got it or why it works ..like this channel ...
Can anybody tell me how to calculate space complexity?
To calculate "Space Complexity", you actually need to look at the extra space used by your algorithm. Also, how is it related to the input.
Refer this: www.geeksforgeeks.org/g-fact-86/ for more information.
Super clever! Thank you!
chutiye
plz hlep
What if out array is like this
int arr[] = {4, 2, 4, 5, 2, 300, 1};
arr[300] would fail, right?
that input is invalid
Actually his input is what is interesting. When are you ever encountering a strict line of following integers?
Given an array of n elements which contains elements from 0 to n-1 is the problem statement
explanation is wrong, it arr[abs(arr[i])]
Geeks for geeks solution vjdeo sucks...
😍😍😍😍😍😍😍😍
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.
for algo to work with 0...inc every element by 1 and while printing decrement it by 1..its already mentioned in the quest that its valid from 0 to n-1....although every algo has pros and cons.........its simply teaches how to think in different directions and wat diff logics can be applied to problems.