Find All Duplicates in an Array | LeetCode 442 | C++, Java, Python

LeetCode Solutions: • LeetCode Solutions | L...
August LeetCoding Challenge: • Playlist
Github Link: github.com/KnowledgeCenterYou...
*** Best Books For Data Structures & Algorithms for Interviews:*********
1. Cracking the Coding Interview: amzn.to/2WeO3eO
2. Cracking the Coding Interview Paperback: amzn.to/3aSSe3Q
3. Coding Interview Questions - Narasimha Karumanchi: amzn.to/3cYqjkV
4. Data Structures and Algorithms Made Easy - N. Karumanchi: amzn.to/2U8FrDt
5. Data Structures & Algorithms made Easy in Java - N. Karumanchi: amzn.to/2U0qZgY
6. Introduction to Algorithms - CLR - Cormen, Leiserson, Rivest: amzn.to/2Wdp8rZ
*****************************************************************************
August LeetCoding Challenge | Problem 6 | Find All Duplicates in an Array | 6 August,
Facebook Coding Interview question,
google coding interview question,
leetcode,
Find All Duplicates in an Array,
Find All Duplicates in an Array c++,
Find All Duplicates in an Array Java,
Find All Duplicates in an Array python,
Find All Duplicates in an Array solution,
442. Find All Duplicates in an Array,
#CodingInterview #LeetCode #AugustCodingChallenge #Google #Amazon #Duplicates

[@mainakbanerjee49]

Very Good technique Sir, Nicely Explained

[@himanshupatel4063]

why we took abs of n .
n is index and we are making the no. at n negative.

[@mandeep2192]

ur background is really intelligently selected as it stops the reflection..& explaination was great..

[@risavkumarjha6899]

Nice Approach,sir
Thanks for sharing.

[@AlokKumar-jh8wp]

Nice explanation sir

[@andreykalmatskiy2656]

When you flip sign you use one bit in the input data, so it's still O(N) space solution.

[@kajalpareek8291]

Can we do sorting first and then check if arr[i]!= arr[i-1] ?

[@KnowledgeCenter]

Yes. That's correct.
But, it will be O(nlogn). In question, they had asked if you are able to do it in O(n) time and O(1) space.

[@akashgupta9863]

But u modified the array
And in Ques there is given that you cannot modified the array

[@rithvikbhat6860]

Fantastic explanation sir🙏

[@KnowledgeCenter]

Thanks

[@shivanshgoyal310]

awesome approach!!

[@KnowledgeCenter]

Thanks.

[@GR8_EDITZZZ]

Just xoring all the elemnts in order to extract the unique elements & store them & them later on xoring this resultant unique elements with the whole array so that we left with only duplicate elements & store & then return them into an array...

[@subhambanerjee6334]

what if we are not allowed to modify the original array?

[@KnowledgeCenter]

You can think in this direction or argue with interviewer on an idea similar to this:
result vector can be in worst case n/2 size. So, O(n). So, we initialize result vector with input vector. Do, the same thing, iterate and make values corresponding to indices negative in result. So, in O(n) we iterate through the complete array. In result positive values denote duplicates, negative values denote single-occurrnces. So, our goal is to get rid of all negative values from result in total O(n) time. So in result take 2 pointers, one from left, one from right. Find the fist left which is negative, and first from right which is positive. Swap the two, and left++, right--, till they cross each other.
When they cross, erase everything from that index till end. Another O(n) time in total.
So, time = O(n)
Space --> 2* result vector and input array is never touched.

[@hereweare644]

What if the array elements are {12,13,...} Like this.. how can we go to the 12th 13th index. Will this solution work for this?

[@ritika2939]

No, the variable nums is in range [1,n] suppose n=5, then the list will contain elements [5,2,3,4,2]. Here, list will not contain element greater than 5. hope u got this

[@Ahmedmeshref12]

Thanks for your effort. I do understand the technique used, but I don't understand why it works??

[@KnowledgeCenter]

Each value - 1, is a valid index in the array, since values are from 1 to n, indices are from 0 to n-1. We traverse the array, whatever value we get, we visit that index. If a value is repeated, we visit that index twice. So, multiplying by -1 is a way of keeping track of visited index. So, if we reach an index having negative value(i.e., already visited) index, we add it to result.

[@hrithikrudra4292]

Isn't it should be nums[nums[n-1]]*=-1.
Please someone help me.Thanks

[@karanjitrandhawa1515]

exactly brother
i was also thinking same only
did you solved?

[@krithik4464]

Why are we using abs(n) ?

[@KnowledgeCenter]

Each value is in range 1 to n. Size of array in range 0 to n-1. So, each value is also a valid index if we subtract 1 from value. So, whenever we get a value, we visit that index, and mark that index as VISITED by negating the existing value.
As as result, we may negate a higher value from lower index, and when we reach there in the process of linear scan, that value is Negative, so not a valid index. So, take abs(n) i.e., the original value, abs(n)-1 again becomes a valid index in array.

[@kwakukusi4094]

thank you very much

[@KnowledgeCenter]

Glad it helped

[@SangelRally]

What tools are you using ?? Black board and Software to write using pen tablet.

[@KnowledgeCenter]

Powerpoint.

[@treksis]

thank you

[@KnowledgeCenter]

Welcome!

[@jay-rathod-01]

Sir this solution was so cool and simplified. I thought of using rabbit and tortoise so went in a wrong direction.
One request: please do explanation and code to check Bipartite.

[@TheMsnitish]

Bhai, naya question ka solution ? Vertical order B Tree. Would like to learn from your example

[@KnowledgeCenter]

Added.

[@TheMsnitish]

@@KnowledgeCenter Thanks

[@SAINIVEDH]

The main condition is not to change the values of given list

[@tulikachhaukhhadiya1666]

sir but this approach at 5:27 won't work when we have nos. repeating thrice

[@PiBiNi]

They have specified that we cannot use exrta space. But result array is extra space right? Please correct me if I'm wrong here

[@KnowledgeCenter]

result is unavoidable, space other than result is what they meant.

[@vishalagarwal9392]

@@KnowledgeCenter why it is avoidable?

[@akshitkushwaha9479]

Here's how Im gonna do it:-
ar = [4,3,2,7,8,2,3,1]
count = []
for i in range(len(ar)):
if ar[i] not in count:
count.append(ar[i])
else:
print(ar[i],'is occuring more than once')

[@jay-rathod-01]

this is dope too.

[@DhananjaySharma-kb7yf]

This is not working with the following input ->
int[] numRay = {17, 27, 11, 23, 14, 29, 17, 24, 3, 6, 18, 8, 18, 16, 29, 11, 24, 5, 0, 1, 28, 3, 28, 4, 13, 7, 7, 27, 10, 21};
Expected solution-> [3, 7, 11, 17, 18, 24, 27, 28, 29]
Actual solution -> [3, 7, 11, 17, 24, 27, 28, 29]
---------------------------------
My solution (instead of multiply, using addition)
int[] numRay = {17, 27, 11, 23, 14, 29, 17, 24, 3, 6, 18, 8, 18, 16, 29, 11, 24, 5, 0, 1, 28, 3, 28, 4, 13, 7, 7, 27, 10, 21};
int constant = numRay.length;
Set solution = new TreeSet();
for (int n : numRay) {
if (n >= constant) {
n = n - constant;
}
if (numRay[n] < constant) {
numRay[n] = numRay[n] + constant;
} else {
solution.add(n);
}
}

[@rajeevranjan-tu3yv]

Not satisfied with the answer. Came here in search of a simple solution that works for any array but found a complex solution.
Can we do it without using a vector or list, with the simple array?
What if we have {102,203, -405, 203, 43, 78, 102, 202}. How we will find the duplicate only using simple array concept?

[@SavaSrikanth]

What If array contain 26 and the array size if 7?

[@rohitbhanot7809]

Check the question constraint, it says 1