Interview Question: Find All Duplicates

[@junhaoxie9945]

Are you gonna do more interview questions? Really love your videos, imo the best interview question channel on KZbin with clearest and best explanation. Please do more!!

[@ByteByByte]

Yep I definitely am. I really appreciate the support and I hate leaving you all hanging! Things have been very hectic at work so I haven't had a lot of time, but I'm going to try to post more regularly. Thanks for hanging in there :)

[@PavelPalancica]

Thanks for the video, Sam! This is my Swift implementation if anyone is interested: (Note that I created a copy of numbers from the beginning, cause I don't want to have any side effect. Plus, Swift won't even allow us to change numbers as is (it's a let constant, unless we add the inout after the colon, which will allow us to change it directly.) func duplicates(numbers: [Int]) -> [Int] { var resultSet = Set() var numbersCopy = numbers for i in 0..

[@ByteByByte]

Thanks for sharing. If you're interested in doing so, I'd love to have you create a PR and add your code on github! github.com/samgh/Byte-by-Byte-Solutions

[@baravi2005]

Really awesome videos Sam...keep them coming!

[@ByteByByte]

thanks :)

[@puneetdawer8657]

What happen if input is [3,1,3] ? Answer should be [3] but with this solution it will give Array index out of bound. Input is satisfying criteria 1

[@brent...]

You have indices 0, 1, and 2. He checks or negates abs(val)-1. The maximum val is 3. abs(3)-1 = 2. 2 is in the set (0, 1, 2). What's the issue?

[@smirkedShoe]

Using a HashSet doesn't make the size O(n) because it's a dynamic data storage and it will vary with the size of input array???

[@ArjunKalidas]

Great explanation! Keep em coming. Thanks a lot. I liked the way you explained the problem solving approach and how you derived an optimized solution starting from brute force.

[@QDem19]

Great solution, but isn't introducing the hashset adding O(N) space complexity, it does not look like O(1) any more.

[@ByteByByte]

We're not counting that because it is just being used to store the final result/what is being returned

[@QDem19]

Okay, now if you were using the Hashset approach instead of the index approach then the hashset would have held the final result as well - so would you call that O(1) as well? I do not mean to start an argument, I would just like a discussion.

[@ByteByByte]

No it's a totally valid question. Basically we don't count the space that is explicitly used to store the input or the output, but every other space we use counts towards our space complexity

[@aleksandarrusinov9974]

Actually in the current solution you DO use additional space because you return a newly created ArrayList from the Set, until the next garbage collection you will have 2 * n additional space n of which is not needed!

[@aleksandarrusinov9974]

Actually you can refactor the function return type to Set instead of List - therefore the user will know that this function returns distinct elements every time.

[@TheSrini007]

I was thinking like counting sort, but the flipping of the sign to encode is even better!

[@umapathybabu8397]

can you use without modifying array?

[@swagatochatterjee7104]

Excellent approach. However the question is how did you come up with this? Is this a general strategy (like prefix sum) then what are some other examples where this strategy is useful? I mean I find array manipulation questions hard, over questions involving Trees and Linked Lists because it appears every Array-ish question involves a different strategy altogether, whereas the Trees and Linked List is about recursive subtree traversal and pointer manipulation respectively.

[@ROFEL]

The encoding solution only works if the numbers in the array are within the size of the array.

[@soudiptadutta6886]

Sam, this method is really good but we can use just HashMap to solve the question also. The solution is : int a [] = {1, 6, 5, 2, 3, 3, 2, -6}; Map map = new HashMap(); for(int i = 0 ; i < a.length;i++) { int r = a[i]; if (map.containsKey(r)) { System.out.println("duplicates => " + r ); }else { map.put(r, 1); } }//for

[@joydas1685]

Simple and easy to understand explanation. Thank you sir. Sir can you post videos on how to use dynamic programming and greedy

[@santokhsingheng]

Perhaps bitset can be used instead of hashset to check for duplicates and would it count as O(1) space? clever solution BTW

[@cloudexpress9694]

This is excellent. Thank you for sharing knowledge for free.

[@daixtr]

I'm curious if there is standard name in the CS literature about this self-referencing short circuit style algo. I saw this concept in other site. Is there a known inventor of this algo?

[@samiahmadkhan2865]

How is your Space Complexity O(1) ? Ain't you using HashSet? (Perhaps O(n) space complex??)

[@ByteByByte]

kzbin.info/www/bejne/fZargJ-qlLaMsJo&lc=UgxrsxFhc6wP7o026WB4AaABAg

[@seniorobjective7649]

While being out of my depth, I'm enjoying these videos a lot. I'm at a point in college where we are focusing in on the high level concept of algorithms and data structures along with some basic implementations, what advice could you give to someone who wants to nail these foundations?

[@ByteByByte]

Here's an overview of how I suggest you approach studying, but feel free to comment or email me if you have any other questions :) www.byte-by-byte.com/optimize-studying/

[@ujurak3899]

It's pass by value, so isn't resetting the array unnecessary?

[@shreejitnair2174]

wow Sam that was a great solution. How does one think through such solutions?? Looking at the approach it made great sense to me but at first glance I could have never been able to conjure up something like this. How does one build such intuition? Does it just come with solving a lot of problems? If we were able to come up with the hashset or sorting approaching and the interviewer expected us to do better would it be ok to ask them for some guidance?

[@ByteByByte]

Check out this post: www.byte-by-byte.com/stuck-on-coding-interview/

[@allinoneuniverse9673]

I had one list which contains n no.of numbers My list = [1,2,3,4,2,2,1,4,4,4,5,5,6,7,6,5] For this list I'm applying absolute techniques. It shows mess values. Do you clarify my question?

[@SmartProgramming]

amazing explanation bro, thanks a lot for sharing this tutorial 👍👍🙂🙂

[@ByteByByte]

thanks!

[@mustapharaimilawal8053]

Awesome video, please do more.

[@vinithalampally1581]

What if there are three duplicate elements it will print same element twice na?correct me if I am wrong..

[@vrushankdoshi7813]

How can we approach the same problem with O(N) and O(1) space without modifying the array ?

[@batmansmk]

Why did you not create an auxiliary structure (boolean array) for clarity and speed? The optimal space aspect of the presented algorithm assumes that we are storing the integer in a suboptimal structure knowing the constraints (aka signed integer instead of unsigned) :) good video anyhow

[@ByteByByte]

That's a valid point, although really that gets rid of the whole challenge of the problem. And there is also overhead of having multiple arrays, but there you go. Proves there are always tradeoffs

[@jlecampana]

One really quick Question Sam: During a Live phone Interview, are candidates allowed to type in their analysis of how to solve a problem like you do, prior to actually typing in the code that solves the problem? -Thanks!

[@eile4219]

I don't think phone interview will ask this question. You should always analysis and discuss with your interviewer. We are not looking for the answer. We are looking for the process. I fail people who just give the answer without saying anything

[@gurmeetchawla8362]

if the purpose is to just find the duplicates then if we keep spitting the element when you find arr[index] < 0 instead of storing it in the result set, that way you don't need to store and also you don't need to scan again.

[@ByteByByte]

What exactly are you suggesting?

[@selvaganesh138]

For the input of [3, 3, 3], this logic return [3] or [3, 3]. i am pretty sure, this returns [3, 3]. But it supposed to be [3]. Am I right.?

[@StarPlatinum3000]

That's why he uses the HashSet data structure. A set can only have one entry even with multiple insertions at the same place. Finally the set is converted to an ArrayList, which turns the result into a standard List.

[@sharmaanshulmca]

For the case [1, 2, 2, 3, 3, 6] the solution is returning only 2, could you confirm me if I am missing something as all the values are 1

[@ByteByByte]

How did you test it? It should work for that case. If you download the code from the github repo (linked in the blog post) it works for the example you gave

[@sharmaanshulmca]

Thanks for your reply, I verified my code by comparing yours. Your solution is working correctly, I had error in my Swift code. Thanks a lot, Your posts are really helpful for me to prepare for interviews.

[@TheZiZaZo]

What if the set was [12 , 3, 2, 12]. That would set the index to 11. Making arr[index] Out of bounds. Or am I missing something?

[@ByteByByte]

That would be an invalid input. Don't forget the invariant: each value 1

[@TheZiZaZo]

Ahhh! Missed that part

[@piyusharmaus]

it fails for test case like [0,1,2,1] too. REPLY

[@PavelPalancica]

That's invalid input too. An array of size 4 can only contain any item(s) from the set { 1, 2, 3, 4 }. None of the input array should contain 0. Pay attention to the details in the problem specification.

[@SarveshDeshmukh]

Keep up the good work!

[@nicolaswolyniec1354]

wow! crazy idea! I love it. thanks a lot :D

[@ByteByByte]

thanks!

[@michaelmast6725]

No reason at all to use the unordered set to store results. You're already making a second pass to restore the input array, just build the result vector during that pass. Saves you a set->vector conversion as well.

[@harshpatel105]

You will have to worry about duplicates in vector for each element, add element only if it's not present. It will make it O(N^2) even we consider vector only

[@babumon5351]

Awesome logic..Thanks

[@ByteByByte]

you're welcome!

[@GaneshShinde-qx2ey]

what if my array contains negative duplicates?

[@ByteByByte]

Read the problem definition again

[@ankitajain4194]

what if array element is negative?

[@ByteByByte]

Then it's not a valid input

[@piyusharmaus]

it doesn't work for test case like [0,1,2,1], gives out of bound error.

[@ByteByByte]

1

[@princeilu96]

can't we modify this program for an arrray including 0 in it?

[@ashutoshbichare]

a=[1,2,3,5,7,3,2] b=[] s=set(a) for i in s: b.append(i) print(b) #output: [2,3]

[@Loppy2345]

Good explanation, much better than Geekforgeeks.

[@ByteByByte]

thanks!

[@MrMikomi]

I was about to say that I didn't get it. But I see now. He's just using the ability to flip the sign of an element's value as a simple boolean. Very clever. I wonder who first came up with this. For all we know it might have been some geezer in 1972.

[@ByteByByte]

"some geezer in 1972" describes most of the algorithms we use

[@dimpalbhatia5037]

How to find common element in each row of 2D array Like we have array 23 96 74 10 85 11 12 96 2 22 96 11 85 52 10 96 Output should be :- 96 becoz 96 is common in all rows How to do this ??

[@ByteByByte]

You tell me. What would be the first step here?

[@MrAkshay2711]

you can apply BFS in matrix

[@maneeshreddy3825]

Great video

[@ByteByByte]

thanks!

[@srjsunny7941]

Good logic.

[@laytonmiller5865]

Yeah Really nice video!

[@ByteByByte]

thanks!

[@brucechen6052]

What about [0,0,0]

[@harshpatel105]

You fuck read the question. Number ranges from 1 to N

[@avinashpathak7563]

what will happen when arr is [10,10,10,0,0,0]

[@StarPlatinum3000]

The question already has the constraint that the numbers will range from 1 to input-size. So this would be an illegal input, or rather, a different problem, where the best solution would probably become a direct "hash map/set for all input numbers" approach. The question is given at: www.byte-by-byte.com/findduplicates/ leetcode.com/problems/find-all-duplicates-in-an-array/

[@LudwigvanBeethoven2]

So if we dont come up with this smart ass solution they decline us? I could guessed first 3 solution. But not the last one.

[@amolgaikwad8937]

Nice!! But how about the case arr[5,5,6]. Here the logic will fail.

[@ByteByByte]

That input is invalid

[@MrStevepm]

Can't you just add every element to the HashSet, convert it, and you're done?

[@ByteByByte]

We're trying to find the duplicated items, though. Not deduplicate the array

[@TechManAkhil]

Your solution does made sense until u said u would use a set at last. Lol. All of the encoding logic got wasted making no much difference from the general O(N) solution.