LeetCode 442. Find All Duplicates in an Array (Solution Explained)

แชร์
ฝัง
  • เผยแพร่เมื่อ 23 ธ.ค. 2024

ความคิดเห็น • 243

  • @quibler7
    @quibler7 ปีที่แล้ว +6

    The only video on the Internet that made me understood this Problem. Efforts are Appreciated 👏🏼

  • @leonardbrkanac9150
    @leonardbrkanac9150 4 ปีที่แล้ว +230

    This is so simple yet it's so hard to see

  • @arthurg5966
    @arthurg5966 4 ปีที่แล้ว +49

    Consider each element as a node with the value as a pointer to the index of the array
    Then run a cycle detection algorithm.
    Questions like this are so addictive and interesting, they fill excitement inside

    • @garyadamos
      @garyadamos 4 ปีที่แล้ว +9

      You have a coding fetish lolol

    • @saurabhdeshpande8450
      @saurabhdeshpande8450 4 ปีที่แล้ว +6

      Appreciate your peculiar way of thinking, BUT... if we wanted to return ANY(only one) of the duplicate numbers then your approach would work. However, we are told to return EVERY duplicate number.
      for example - nums = [4,3,2,7,8,2,3,1]
      You might end up in infinite loop because you'd need some base condition to stop. But, according to your explanation you would calculate first duplicate number (say 3) and again do the same thing where you might again calculate the previous duplicate number(i.e. 3). If let's say on the second time you calculate different duplicate number (i.e 2), on the third iteration you'll again calculate 2 or 3 because there is no way for you to know how many duplicates numbers are there.
      Correct me if I'm wrong.

    • @z08840
      @z08840 3 ปีที่แล้ว

      @@saurabhdeshpande8450 cycle detection in graph implies using visited list, and it's not O(1) space solution, though it would work

    • @itsJustJayMusic
      @itsJustJayMusic ปีที่แล้ว +1

      @@saurabhdeshpande8450 ik I'm two years late, but, I was trying to apply floyd tortoise algorithm - which OP mentioned - the whole day and I found out eventually exactly what you said, you can't find a base condition (base case) to stop, so you can't apply it many times to find multiple duplicates(considering that you pop the duplicates each time you find one, so you won't be stuck in an infinite loop), if you wanted to iterate or to do it recursively you would need a base condition/case. which makes applying the algorithm hard/impossible with constant space.
      P.S. sry if my writing is too messy. hope I delivered my idea correctly.

  • @visheshmangla8220
    @visheshmangla8220 4 ปีที่แล้ว +9

    Maybe a fine enough explanation is that we needed some way to keep track that an element is visited. Whenever we hit an element, the indicator that an element has been visited is given by negating the value at its index like if you see a 4 you go to its index which is 4-1 and negate it but what if 4 is found again , you check that if you have already negated it and you can catch it to be a duplicate. But you have negated a value to demarcate "visited" which has spoiled the index therefore take absolute to get the correct index.

  • @JohnDlugosz
    @JohnDlugosz 4 ปีที่แล้ว +8

    In your solution, don't forget to put the input back the way it was. The caller is not expecting to have the input trashed when you call a function on it.
    In C++, I would have the input declared `const` so you could not mutilate it in this manner. A tidy solution would be to use the _output_ array for scratchwork.
    Resize the output to match the input. Scan the input and increment the output index based on the input number. Then scan the output and for every '2' you find, put that index at the front of the array. Resize the output to trim to the length of the results.

    • @aadityabhetuwal5990
      @aadityabhetuwal5990 3 ปีที่แล้ว

      cheeky solution but it may not please the interviewer

    • @pant1371
      @pant1371 3 ปีที่แล้ว

      the input gets passed as a parameter to the stack, meaning that it gets destroyed after the function ends,even if it is modified inside it. This happens in C,at least. In other languages,like python,js,php etc, it doesn't because arrays bevahe as pass by reference. You can easily overcome it though by passing a copy of the array as a parameter

    • @pant1371
      @pant1371 3 ปีที่แล้ว

      @ghost mall actually i was kinda wrong in my comment. In all languages, everything that gets passed as an argument to the function, gets copied in the stack and is destroyed when the function terminates. In C's case, suppose you have an array and you pass it as an argument to the function. Passing it to the function, is like passing the address of the first element of the array(&array[0]). If you modify this pointer inside the function(say for example you make it point to a different address), this change will not depict in the main. If,however, you change the element the pointer refers to( *(arr+0) = 100 ), the change will depict in the main. So, it is a pass by value as far as the pointer is concerned, but a pass by reference as far as the values of the pointers(array) are concerned. The safest way,is to create a copy of the array(in C's case) or the list( in python's case(l=l[:]) ) before passing it to a function,even if it is void. It's the same with Java, when you pass an object to a method, if you change it's member variables,the changes will affect the caller even though the copy of the object will get destroyed after the method ends

    • @jamesugbosanmi1154
      @jamesugbosanmi1154 3 ปีที่แล้ว

      @ghost mall can I pair program with you

  • @SB-bt5mm
    @SB-bt5mm 4 ปีที่แล้ว +33

    Hey Nick, that was a great technique and explanation. Do you have a git repo of all the Leetcode problems you've solved so far ?

  • @user-pe9qg3hg3k
    @user-pe9qg3hg3k ปีที่แล้ว

    I think the biggest benefit of Leetcode is the conversation it can encourage. Yes, you can slug away and try to solve it, but to converse is to understand, and to prove understanding. This is surely its own benefit in the coding interview

  • @iamnoob7593
    @iamnoob7593 5 ปีที่แล้ว +17

    Brilliant,Never Thought of this.Thanks Nick,Keep making videos like this.

  • @ryzen980
    @ryzen980 4 ปีที่แล้ว +66

    Damn....this guy is a genius!!!! Though he looks lazy all the time!!

    • @udaykumar-cx9lu
      @udaykumar-cx9lu 4 ปีที่แล้ว

      😆😆

    • @lugiadark21
      @lugiadark21 4 ปีที่แล้ว +3

      Hahahaha I do not know if this is a good comment or a bad comment

    • @adithyavarambally6494
      @adithyavarambally6494 4 ปีที่แล้ว

      Actually this is kinda like floyd's tortoise and hare cycle problem..But yeah, dudes amazing

  • @halcyonhimanshu
    @halcyonhimanshu 4 ปีที่แล้ว +63

    How do solutions like these come naturally? It’s very difficult to think in that direction unless I know the solution beforehand.

    • @sangramjitchakraborty7845
      @sangramjitchakraborty7845 4 ปีที่แล้ว +48

      It's about practice and watching lots of clever solutions like this. You have to extract every little clue from the problem statement. For example the fact that the numbers are between 1 and the length of the array points to the direction that the solution perhaps has something to do with indices of the array, as subtracting 1 from any value in the array will give you a valid index. Also they ask you to do it in no extra space. That leads to the belief that maybe the given array has to be mutated. The solution still does not follow naturally but with some thought you could maybe get an idea of how it might be solved.

    • @clodgozon3968
      @clodgozon3968 4 ปีที่แล้ว +4

      This is what I had in mind.

    • @borat_trades2860
      @borat_trades2860 4 ปีที่แล้ว +1

      @@sangramjitchakraborty7845 yes exactly! it boils down to just SEEING, OBSERVING, many tricks - then when i encounter similar problem - i loop through all of my 'clever tricks' stored in my mind and find something similar.

    • @Auzep
      @Auzep 4 ปีที่แล้ว +11

      Welcome to the stupid world of tech interviews. You need to know how to reverse a binary tree for a job where you're going to change csv's manually. Programming is made more unnecesary difficult with all the bullshit at tech interviews.

    • @AniketSomwanshi-ll7mz
      @AniketSomwanshi-ll7mz 4 ปีที่แล้ว

      @@Auzep Do u think this is to filter the competition ?

  • @rajeshseptember09
    @rajeshseptember09 2 ปีที่แล้ว +4

    Hey Nick. Great solution, but what if the original array needs to remain un-mutated (not modified). In this solution, we are actually modifying the original array, isn't it ?

  • @ShubhamKumar-fy1fl
    @ShubhamKumar-fy1fl 4 ปีที่แล้ว +3

    I seriously Love your videos. You make explanation very clear. LOVE from India.❤

  • @BadriBlitz
    @BadriBlitz 3 ปีที่แล้ว +1

    Well Explained Nick.The Tracing of the code is something that really helped.Very Helpful Video.

  • @JohnSmith-xf1zu
    @JohnSmith-xf1zu 3 ปีที่แล้ว +7

    I was thinking of something else. If you use some clever swapping in addition to negatives, you can make sure you only list each duplicate once. With the current example, if there are five 2's, it will list it four times in the results.
    Basically, loop over each index. For each index, while not duplicate or not in the correct index, continually swap the current number into it's correct index. If there is already the correct number in the correct index, then we have a duplicate, so flag the number in the correct index as negative. If already negative, then don't add it to the output list. In any of those cases, move to the next index, skipping indexes that already have the correct number. This algorithm would also be O(n) and only list each duplicate once.
    I made a trace out of the example in the video, but replacing 8 with a 2 for an extra duplicate: [4,3,2,7,2,2,3,1]
    Using 1 based indexing for simplicity.
    index: 1, output: []
    [4,3,2,7,2,2,3,1]
    [7!,3,2,4!,2,2,3,1] 4 detected. swaped index 1 and 4
    [3!,3,2,4,2,2,7!,1] 7 detected. swaped index 1 and 7
    [2!,3,3!,4,2,2,7,1] 3 detected. swaped index 1 and 3
    [3!,2!,3,4,2,2,7,1] 2 detected. swaped index 1 and 2
    [3,2,-3,4,2,2,7,1] duplicate of 3 detected at index 1 and 3. Mark negative, add output, and continue.
    index: 2, output: [3]
    [3,2,-3,4,2,2,7,1] 2 is at correct index. Continue
    index: 3, output: [3]
    [3,2,-3,4,2,2,7,1] 3 is at correct index. Continue
    index: 4, output: [3]
    [3,2,-3,4,2,2,7,1] 4 is at correct index. Continue
    index: 5, output: [3]
    [3,2,-3,4,2,2,7,1]
    [3,-2,-3,4,2,2,7,1] duplicate of 2 detected at index 2 and 5. Mark negative, add output, and continue.
    index: 6, output: [3, 2]
    [3,-2,-3,4,2,2,7,1] duplicate of 2 detected at index 2 and 6. Already marked negative, so continue.
    index: 7, output: [3, 2]
    [3,-2,-3,4,2,2,7,1] 7 is at correct index. Continue
    index: 8, output: [3, 2]
    [3,-2,-3,4,2,2,7,1]
    [1!,-2,-3,4,2,2,7,3!] 1 detected. swaped index 8 and 1
    [1,-2,-3,4,2,2,7,3] duplicate of 3 detected at index 8 and 3. Already marked negative, so continue.
    Note: It doesn't matter that we already counted this 3 as a duplicate, since we are only counting duplicates once anyway.
    And done. We have our output list, containing 2 and 3 exactly once, even though '2' had 2 duplicates.
    Since every check moves a number to the correct index, we only need to do N swaps at most for the whole array. We also guarantee that all numbers to the left of the current index are either in the correct index or are duplicates. So this algorithm ends up being O(2n) at most if no duplicates and O(n) at best if all duplicates.

    • @shreeharjoshi6143
      @shreeharjoshi6143 2 ปีที่แล้ว

      Only if you had read the question properly, you would not have overthought. It clearly states a value can appear at most twice.

  • @djfedor
    @djfedor 5 ปีที่แล้ว +19

    Hey Nick, great video, thanks for sharing!
    How much time do you spend usually on solving a problem by your own before you realize that you’re stuck and have to check discussions?
    Is it worth to try harder and solve something on your own for another two days before going through discussions?

    • @NickWhite
      @NickWhite  5 ปีที่แล้ว +10

      Stanislav Fedosov 2 days dude haha nooo not even 2 hours

    • @NickWhite
      @NickWhite  5 ปีที่แล้ว +22

      If I’m not coming up with a for sure optimal solution in an hour then I’m checking discussion

    • @mandeepubhi4744
      @mandeepubhi4744 4 ปีที่แล้ว

      @@NickWhite thanks, i was in dilemma too.

  • @ThatDereKid
    @ThatDereKid 4 ปีที่แล้ว

    If there was a solution that modified the method parameter (mums) itself and returned that, is that considered to be less space that declaring a separate vector variable as done here and returning that? Or is it the same?

  • @divyakumar9393
    @divyakumar9393 4 ปีที่แล้ว

    who is Gail Walman with Alice? Nick mentions it at 3:10.
    Where can I find those videos?

  • @MechanicalThoughts
    @MechanicalThoughts 4 ปีที่แล้ว +3

    Genius solution. Thanks for the explanation before the code.

  • @vrushankdoshi7813
    @vrushankdoshi7813 4 ปีที่แล้ว +7

    Hi Nick,
    How can we approach the same problem without modifying the array in 0(N) time and 0(1) space?

    • @GouravSingh
      @GouravSingh 4 ปีที่แล้ว

      use Unordered_map !

    • @muktadirkhan6674
      @muktadirkhan6674 4 ปีที่แล้ว

      @@GouravSingh thats not O(1) space.

  • @kevinclark443
    @kevinclark443 4 ปีที่แล้ว

    Finally! I was able to solve one and then came here to look how that you did it. This is how I solved it:
    function findDuplicates(nums: number[]): number[] {
    let result = nums.reduce((prev, current) => {
    if (prev[1].find(n => n === current)) {
    prev[2].push(current);
    } else {
    prev[1].push(current);
    }
    return prev;
    }, { 1: [], 2: []})
    return result[2];
    };
    Runtime: 2024 ms, faster than 16.67% of TypeScript online submissions for Find All Duplicates in an Array.
    Memory Usage: 47 MB, less than 100.00% of TypeScript online submissions for Find All Duplicates in an Array.
    Then made it much faster, but still 16.67% hmm
    function findDuplicates(nums: number[]): number[] {
    let result = nums.reduce((prev, current) => {
    if (prev[1][current]) {
    prev[2].push(current);
    } else {
    prev[1][current] = true;
    }
    return prev;
    }, { 1: {}, 2: []})
    return result[2];
    };
    Runtime: 144 ms, faster than 16.67% of TypeScript online submissions for Find All Duplicates in an Array.
    Memory Usage: 47.6 MB, less than 100.00% of TypeScript online submissions for Find All Duplicates in an Array.

  • @samuelonyeukwu4583
    @samuelonyeukwu4583 4 ปีที่แล้ว

    I didn't get what he said at 3:09 who's videos?

  • @juliahuanlingtong6757
    @juliahuanlingtong6757 3 ปีที่แล้ว

    Will the technique works for array contains negative numbers as well? say one of the duplicates is a negtive number. According to the logic, it doesn't seem to work.However the test run printed out has negative number array

  • @videos2laugh961
    @videos2laugh961 ปีที่แล้ว

    can this question be done with binary XOR operation?

  • @alexwexov4298
    @alexwexov4298 3 ปีที่แล้ว

    What font is this ? Looks very pleasing.

  • @dayvie9517
    @dayvie9517 4 ปีที่แล้ว +4

    How to solve a problem for natural numbers without zeros which never occurs.

  • @tundeadebanjo6579
    @tundeadebanjo6579 3 ปีที่แล้ว +1

    I solved this using two pointers to check where there is equal values. One counting from the left and the other counting from the right.

    • @spidermanclips7966
      @spidermanclips7966 3 ปีที่แล้ว

      i did the same thing , his solution is pretty tricky

  • @luckyismynickname
    @luckyismynickname 4 ปีที่แล้ว +2

    What a amazing video 😲😲 please do more like that. It will help us to build our logics.

  • @242deepak
    @242deepak 9 หลายเดือนก่อน

    The main idea is :
    Since the array contains integers ranging from 1 to n (where n is the size of the array), we can use the values of the elements as indices. This allows us to associate each element with a specific position in the array. So if a position is referenced more than once it indicates that there is a duplication.

  • @prezmoten
    @prezmoten 5 ปีที่แล้ว

    Great Job! How did you generate this trace of the problem? Is there such option on leetcode?

  • @ddiverr
    @ddiverr 4 ปีที่แล้ว +1

    Is there a way to do this in O(n) without having duplicates in the output array, whenever the number of duplicates of any number in the original array is even (Excluding 2)?

    • @Mrwiseguy101690
      @Mrwiseguy101690 4 ปีที่แล้ว

      I guess you can use a HashSet and then convert it to an ArrayList at the end, but then it wouldn't be constant space anymore.

    • @soggy6645
      @soggy6645 4 ปีที่แล้ว +1

      There'd be no point with such a modification since this specific scenario limits duplicates to 2 occurrences. If it were any number of occourences though,You could remove line 6 and then have a second loop outside of the first add only the negative numbers to the output array.
      It becomes O(2n), but that just simplifies down to O(n).

  • @damodaranm3044
    @damodaranm3044 5 ปีที่แล้ว +3

    it took me like 40 mins to understand but worth the time

    • @butterman4091
      @butterman4091 4 ปีที่แล้ว

      Took me the first try to understand. I dont even know java script i just know C. Its pretty fun.

  • @adithiyagurupatham3255
    @adithiyagurupatham3255 3 ปีที่แล้ว

    What should be the approach if the array elements cannot be modified

  • @helmialfath9897
    @helmialfath9897 4 ปีที่แล้ว +2

    I have no idea how this solution just came to u. Brilliant

  • @zarovv5589
    @zarovv5589 4 ปีที่แล้ว

    if i could do it with a list or an array max size n i can basically allocate and array of n, go through the input array and update indexes with the counter with the amount of times i saw the number. then i can just go through the array and print the indexes with count greater than 1.

  • @sivajik
    @sivajik 4 ปีที่แล้ว

    really brilliant solution. Sounded like Floyd's tortoise and hare algorithm but pretty simple to understand.

  • @sivaganesh4489
    @sivaganesh4489 4 ปีที่แล้ว

    Awesome nick but what if there is multiple duplicates(like 4) in these output arr also contains duplicates for this solution right???

    • @dileshsolanki2383
      @dileshsolanki2383 4 ปีที่แล้ว

      as given in this question - it will have numbers occurring either once or twice.

  • @iMagUdspEllr
    @iMagUdspEllr 9 หลายเดือนก่อน

    Record the fact that you have seen a value x by making the value y located at index x - 1 negative. If the value stored at an index is already negative, this means you have already seen that value and you can append current_index + 1 to your list of duplicates.

  • @Ownage4lif31
    @Ownage4lif31 4 ปีที่แล้ว

    But what if the numbers were bigger than the arrays length? You'd have to assume each number in the array an access an index. Would you not?

  • @GaebRush
    @GaebRush 4 ปีที่แล้ว

    You are using array lists to store the duplicate values. Array lists have access comlexity O(1) but adding items is very expensive because the underlying array has to be extended. Linked lists however have O(1) adding complexity. And since you don’t access specific indices in the output array it would make it faster to use a LinkedList for the output array

    • @shreevatsalamborghin
      @shreevatsalamborghin 4 ปีที่แล้ว

      GaebRush the question gives us to fix the given method already

    • @IvanRandomDude
      @IvanRandomDude 4 ปีที่แล้ว

      Or you can just allocate new list with nums.length/2 initial capacity

  • @Parallaxxx28
    @Parallaxxx28 ปีที่แล้ว

    How would we solve this if the maximum integer in the array is greater than the size of the array

  • @smartcoder4854
    @smartcoder4854 4 ปีที่แล้ว

    What about array of booleans. Will check true if it is coming twice otherwise false by default. I think this is simpler than negative values

  • @duilioray6299
    @duilioray6299 4 ปีที่แล้ว

    Hi thanks for this video! I also solved this problem but I did not use an extra list, I just modified the original list and then returned it. To count the elements that were repeated I substracted N to the position represented by the value, so then if value + 2*n is lower than N then I found a repeated element.
    Are you sure that using an output list is accepted as no extra space? Considering a solution that only uses the original list is also possible.

    • @rajivnarayan5214
      @rajivnarayan5214 4 ปีที่แล้ว

      Hey Duilio what do you mean by 'subtracting N', so I assume N is the largest element in this case is 8. In this example the first element is 4, assuming that you mean the position representing by 4 is the 4th element which is 7, you subtract 8 from 7 -> 7 - 8 = -1, then when traversing you add back 8 if you are -9 + 2*8 = 7 < 8 therefore there is a repeat?

    • @duilioray6299
      @duilioray6299 4 ปีที่แล้ว +1

      @@rajivnarayan5214 thanks for replying, yeah that's what I mean

    • @rajivnarayan5214
      @rajivnarayan5214 4 ปีที่แล้ว

      I assume you only do the subtraction once right? If that is the case then isn't your solution exactly the same as the video's?

  • @sapnilpatel1645
    @sapnilpatel1645 2 ปีที่แล้ว

    Thank you so much @Nick White Your video is very much helpful for me.

  • @warmpianist
    @warmpianist 4 ปีที่แล้ว

    What if it's an unsigned int that we cannot use nums[i] = -nums[i]? We can't do nums[i] = nums[i]+n because of the possible overflow at n >= 2^31

    • @embedded_software
      @embedded_software 3 ปีที่แล้ว

      Perhaps you can ask your interviewer if you can make assumptions about the maximum size of the input array. An array with 2^31 elements would be enormous. I suppose if you do need to consider arrays of that size, this method wouldn't work.

  • @haqtechnofox
    @haqtechnofox 4 ปีที่แล้ว +1

    Can we use the hashset for this scenario? What will be the difference... Love your videos ❤️

    • @narayanbhat3279
      @narayanbhat3279 4 ปีที่แล้ว +11

      Hashset occupies space..and we are required to solve it in O(1) space complexity

    • @marketcrorepati5729
      @marketcrorepati5729 2 ปีที่แล้ว

      if you use hashset in interview you will pass because it's a gotcha problem

  • @satk2554
    @satk2554 4 ปีที่แล้ว

    Who is the person that he mentioned about her videos in the beginning of the video 3:05 ?

    • @ayushsbhatt6145
      @ayushsbhatt6145 4 ปีที่แล้ว +2

      Gayle Laakmann McDowell. She is the author of Cracking the coding interview.

  • @kevinrobinson6685
    @kevinrobinson6685 5 ปีที่แล้ว +1

    Does sorting the array count as extra space?

    • @dailyinspirationwithmenaagina
      @dailyinspirationwithmenaagina 5 ปีที่แล้ว

      Yes o(n) space

    • @DanielNit
      @DanielNit 4 ปีที่แล้ว +1

      @@dailyinspirationwithmenaagina sorting doesn't always allocate extra space. Most casual sorting algorithms alter the set itself and don't allocate new.
      Though the main reason not to sort beforehand is that your time complexity goes up to like O(n log n) or worse, and the goal was O(n).

    • @powerfulyeet2537
      @powerfulyeet2537 4 ปีที่แล้ว

      Nah library sorting algorithms will pretty much always be done in-place

  • @gdeep5124
    @gdeep5124 4 ปีที่แล้ว

    I tried something but don't know if its a correct solution or not. The function below checks for any given count of occurance:
    vector FindOccur(vector arr, int occur) {
    vector ele;
    Int l=0, r=0, arr_size=arr.size(), curr_occur=0;
    While(l=arr_size) {
    If(curr_occur == occur) {
    ele.push_back(arr[l]);
    }
    l++; r=l; curr_occur=0;
    }
    If(arr[l] == arr[r]) {
    curr_occur++;
    }
    r++;
    }
    return ele;
    }

  • @felix2uber200
    @felix2uber200 4 ปีที่แล้ว

    Hey, Someone help
    if anyone is reading the comments and is good at this, (i know this would be a worse solution but it is one I managed to come up with quickly and wanted to check) would it work to just, run through the input array, and for each number seen, add onto the output array in the number's index (minus 1) the length + 1, and then, when finding a duplicate and checking the index minus one, if there was already a number there then it would be replaced with the duplicate. at the end, all cells equal to length + 1 would be removed. return.
    any feedback?

  • @jonathanho618
    @jonathanho618 5 ปีที่แล้ว +3

    good solution, original array was correct [3,2] however

  • @vslaykovsky
    @vslaykovsky 4 ปีที่แล้ว +8

    This should be done in-place to avoid extra memory allocation

  • @damodaranm3044
    @damodaranm3044 5 ปีที่แล้ว +4

    man how do u got all these knowledge . where have you learned all these things

    • @hacker-7214
      @hacker-7214 4 ปีที่แล้ว +2

      Same exact question

  • @chrono8233
    @chrono8233 3 ปีที่แล้ว

    How do you find duplicate pairs and trips of numbers within an array?

  • @MrCitizen00
    @MrCitizen00 4 ปีที่แล้ว

    Hey Nick this can also be done in a single line if count method is allowed I believe, otherwise another algo may be if we sort the given list and then fire a single loop and check the next element and if two are equal than we can enter it in new array if that element is not there in new array...and boom we get an array of all repeated elements in a simple elementary logic..🙌.what do u think..?

    • @kushalbaldev8490
      @kushalbaldev8490 4 ปีที่แล้ว +1

      sorting would take an extra time complexity..!!

  • @sars-cov-2611
    @sars-cov-2611 4 ปีที่แล้ว

    I paused before the video started.. using javascript, I'd loop through the array: for each element, i'd subtract the ith element to all the other elements and look for zeros. If exactly 2 zeros are found, then that's one of the pairs. The operation takes (n-1)! time to complete, so approximately O(n!). Now to watch the video to see how to do it within time complexity of O(n).

  • @abbasramish5803
    @abbasramish5803 4 ปีที่แล้ว +2

    Thats brilliant one. This made my day

  • @madhuragadgil2617
    @madhuragadgil2617 4 ปีที่แล้ว +1

    Let's say, we were asked to find the missing numbers instead of the duplicate. Can we use this approach to come up with a similar approach to solve that? If you know of this or have done this, could you post a video for that as well?

    • @shivikasharma11
      @shivikasharma11 4 ปีที่แล้ว

      mark the numbers -ve once (if they are already marked leave them), Then return the list like return [id+1 for id, num in enumerate(nums) if num > 0]

  • @yanivsh
    @yanivsh 3 ปีที่แล้ว

    Line 7 should be in Else, also for correctness there should be another final loop making all negative elements positive at the end

  • @eliy5550
    @eliy5550 4 ปีที่แล้ว

    Thanks to people like you I will have a degree

  • @IvanRandomDude
    @IvanRandomDude 4 ปีที่แล้ว +2

    We should definitely allocate output_arr list with initial capacity of nums.Length/2 to avoid excessive reallocation (log(n) of them)

    • @AnthonyLauder
      @AnthonyLauder 4 ปีที่แล้ว +1

      you would need ceiling of length/2

  • @muffinberg7960
    @muffinberg7960 3 ปีที่แล้ว

    You need to return the input array. "What else am I supposed to return?". It is the input array, here you create additional space.

  • @VeereshPradeep
    @VeereshPradeep 4 ปีที่แล้ว

    This is a brilliant solution Nick!

  • @vinayyelleti2714
    @vinayyelleti2714 4 ปีที่แล้ว

    how can we solve for list which has both negative and positive integers...? -n1 ≤ a[i] ≤ n2

  • @jagicyooo2007
    @jagicyooo2007 4 ปีที่แล้ว +1

    the only thing that doesn't make sense is why an element at a specific index will point to another index with the same value?
    for example: [1, 2, 3, 2]; how does index 3 know index 1 has the same value?

    • @denifelixe
      @denifelixe 4 ปีที่แล้ว

      Index 1 will mark the value (in this case 2) to negative on its turn (loop i), so when the turn comes to index 3, the index 3 checking if index 1 is negative, if negative then the value (in this case 2) is duplicate

    • @jagicyooo2007
      @jagicyooo2007 4 ปีที่แล้ว

      @@denifelixe why does index 3 check index 1? how does index 3 know index 1 has the same value?

    • @denifelixe
      @denifelixe 4 ปีที่แล้ว

      Because index 3 has value 2 and the formula is value-1, so 1

    • @denifelixe
      @denifelixe 4 ปีที่แล้ว

      Why we do minus 1? Because if we have integer 4, we dont have index 4 since it out of bounds

    • @kushalbaldev8490
      @kushalbaldev8490 4 ปีที่แล้ว

      This solution can be applied for the specifically to this the problem only..!!

  • @kervensjasmin1508
    @kervensjasmin1508 4 ปีที่แล้ว

    Hashmap and loop.
    For loop with two pointers.

  • @prabhavdixit3639
    @prabhavdixit3639 2 ปีที่แล้ว

    ArrayList list = new ArrayList();
    Arrays.sort(nums);
    for(int i=0;i

    • @MinhTran-jg2bx
      @MinhTran-jg2bx 2 ปีที่แล้ว

      sorting is not O(n) anymore

    • @prabhavdixit3639
      @prabhavdixit3639 2 ปีที่แล้ว

      ​@@MinhTran-jg2bx Yep that is true, n(log(n)) now.

  • @rafaspimenta
    @rafaspimenta 3 ปีที่แล้ว

    The problem is the short time to think and build the solution, these online tests were made to be copied from the internet. Which is a good skill too

  • @Mike-ci5io
    @Mike-ci5io 2 ปีที่แล้ว

    I initially though of replacing the duplicates with 0 and realized I needed to remember the numbers... the only way to preserve the numbers while tracking duplicates is to negate them in O(1) space ...clever

  • @MaheshKumar-yz7ns
    @MaheshKumar-yz7ns 4 ปีที่แล้ว +1

    you are super genius bro!

  • @Fatality_Retired
    @Fatality_Retired 3 ปีที่แล้ว

    Wow. That was awesome. Liked and subscribed 🙂

  • @Cyborg1170
    @Cyborg1170 2 ปีที่แล้ว +1

    Hey Nick. Where's your Discord link. I just got into high school. Did a bunch of LeetCode and Amazon has given me an offer. Thanks for your videos. I am going to be making more than both my parents combined.

  • @Unknown373d
    @Unknown373d 9 หลายเดือนก่อน

    great explination in the end

  • @harir7676
    @harir7676 4 ปีที่แล้ว

    noob here, where is the main function and which part of the code stores the input array ?

  • @ncba
    @ncba 2 ปีที่แล้ว

    I am still stuck at the question, whats linear solution and extra space?

  • @ameyamahadevgonal8130
    @ameyamahadevgonal8130 4 ปีที่แล้ว

    why are making the num[index] = -num[index] again
    means -3 -> +3
    why again making it positive

    • @kat1345
      @kat1345 4 ปีที่แล้ว

      we are never making it positive again because the total of each number can be at most 2

    • @kat1345
      @kat1345 4 ปีที่แล้ว

      if we come across a duplicate, we just check if the value of the index is negative

  • @sumitvelaskar
    @sumitvelaskar 4 ปีที่แล้ว +1

    what would be the solution if the array is immutable

  • @anirbandas12
    @anirbandas12 2 ปีที่แล้ว

    Initially i thought hashmap or frequency array would be good but then the array length could be as long as say 1000 and numbers could be like [1, 99, 999 ...] so hashmap is not good for given space complexity

  • @ashenone5774
    @ashenone5774 3 ปีที่แล้ว

    Thanks brilliant, big ups Nick!

  • @manidhar334u
    @manidhar334u 2 ปีที่แล้ว

    why not using HashMap?

    • @Sheikhhamiz
      @Sheikhhamiz 9 หลายเดือนก่อน

      because it takes extra space 🤷‍♂

  • @omarmostafa6081
    @omarmostafa6081 4 ปีที่แล้ว

    Genius!
    Please, keep going solving more

  • @zzzz26526
    @zzzz26526 3 ปีที่แล้ว

    2:15 is the greatest lifehack ever

  • @dainmart_official4005
    @dainmart_official4005 3 ปีที่แล้ว

    this code not working for [1,1] ?

  • @Harsh-rm1tp
    @Harsh-rm1tp 4 ปีที่แล้ว

    what if the element is greater than the size of the array..?

    • @lasergamer2869
      @lasergamer2869 4 ปีที่แล้ว

      U use Floyd’s Hare and Toritoise algorithm ?

  • @arslan113
    @arslan113 5 ปีที่แล้ว

    O(n'2) .length is consuming n times each call -- you should have assigned it!??

    • @williambillemeyling5647
      @williambillemeyling5647 4 ปีที่แล้ว

      .length is constant time

    • @arslan113
      @arslan113 4 ปีที่แล้ว

      @@williambillemeyling5647 yep my bad, I blame c😂

  • @uditkumar7211
    @uditkumar7211 2 ปีที่แล้ว

    great explanation

  • @thatonedude4926
    @thatonedude4926 4 ปีที่แล้ว

    Excuse me, can someone explain to me what extra space is?

    • @brandonkirincich8181
      @brandonkirincich8181 4 ปีที่แล้ว

      Extra space in memory.

    • @thatonedude4926
      @thatonedude4926 4 ปีที่แล้ว

      @@brandonkirincich8181 i see, the extra space by creating a new instance of arraylist?

    • @lokeshisrani8827
      @lokeshisrani8827 4 ปีที่แล้ว

      @@thatonedude4926 Yes. Whatever space you require to store the another array or variable other than output array.

  • @rupalims
    @rupalims 4 ปีที่แล้ว

    HOw to paste the trace

  • @abineshsubramani2592
    @abineshsubramani2592 4 ปีที่แล้ว

    what happens if number is repeated thrice?
    We can use Set to include this kind of test case also

  • @arpit8273
    @arpit8273 4 ปีที่แล้ว

    Great explanation bro

  • @ManishPushkarVideos
    @ManishPushkarVideos 4 ปีที่แล้ว

    I got this exact question asked in my coding interview

  • @ommy1988
    @ommy1988 4 ปีที่แล้ว

    What if the index 3 have the value 4

    • @kushalbaldev8490
      @kushalbaldev8490 4 ปีที่แล้ว

      It won't work the algo is suitable by looking into the pattern as [4,3,2,7,8,2,3,1] so you can clearly see that index from left and right that is 3 from left and 3 from right 2 from left and 2 from right. I think you got the point..!!

  • @ajayapat2702
    @ajayapat2702 4 ปีที่แล้ว

    great explanation.

  • @rashedulislam9301
    @rashedulislam9301 5 ปีที่แล้ว +1

    Thanks a lot.

  • @himanish2006
    @himanish2006 4 ปีที่แล้ว

    Awesome video!!

  • @tannerbarcelos6880
    @tannerbarcelos6880 4 ปีที่แล้ว +5

    Why am I not clever enough lmao

  • @Grassmpl
    @Grassmpl 3 ปีที่แล้ว

    Just negate the element corresponding to the element seen the first time. If the position is negative you seen it twice.

  • @sipwhitemocha
    @sipwhitemocha 2 ปีที่แล้ว

    Nick White: "It's easy, guys. Just pay 5 bucks to get 'Solution' and code this shit"

    • @sipwhitemocha
      @sipwhitemocha 2 ปีที่แล้ว

      nums = "----->-->"; k =3
      result = "-->----->";
      reverse "----->-->" we can get "

  • @codeLine7
    @codeLine7 8 หลายเดือนก่อน

    nice explanation

  • @ninedux
    @ninedux 4 ปีที่แล้ว

    thats bloody clever...awesome

  • @danilobucker
    @danilobucker 5 ปีที่แล้ว

    What is Math.abs ?

    • @tsoodoltse4259
      @tsoodoltse4259 5 ปีที่แล้ว

      it converts negative number to positive one. For instance, Math.abs(-1) is 1.

    • @DanielNit
      @DanielNit 4 ปีที่แล้ว

      What it does has been said already so maybe I could add to the name.
      First of all, it used the Math namespace, which has functions assigned for mathematical operations.
      The abs stands for absolute, which has been explained by Tsoodol Tse already.
      (Sorry if that was too obvious. Just trying to clear things up for newcomers)