Find All Numbers Disappeared in an Array - Leetcode 448 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/find-al...
Python Code: github.com/neetcode-gh/leetco...
0:00 - Read the problem
0:49 - Drawing Explanation
6:38 - Coding Explanation
leetcode 448
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#microsoft #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@Ryanamahaffey]

This one was a bit hard to grasp at first until I saw the code!
Great video regardless, but I think a better test case to explain would have been [1, 4, 4, 2].
Seeing you go back and mark idx 1 (for the number 2) as a negative 4 would have made things much clearer for me!

[@meowmaple]

Previously had done this question but not in the O(1) space complexity way, and wow I must say that this is such an interesting way of making it O(1) space complexity!

[@boris---]

Yeah I can go back to McDonald if this is easy question....

[@huckleberryfinn8795]

Its easy for a senior software engineer 😂

[@nikhilchauhan5837]

Constant space problems are always tricky i got this one in interview 😔. Can you make more videos on solving constant space problems

[@leetcodeespanol59]

Thanks for all your hard work Neetcode! Its great to see you consistently upload videos for us! Keep it up!

[@hussamq9909]

Great explanation, you never disappoint. Keep up the good work.

[@BROOKnim]

if some people dont understand this very clearly, there is this sorting technique called cyclic sort ( sorts array in O(n) if elements are in range of [1,n] ). look it up , will be useful.

[@danielcustduran]

I never figured out this approach. I solved it using sets but this doesn't meet the constraint of space complexity. Great!!!

[@ngneerin]

Keep up the leetcode!

[@OmarChida]

I immediately though of cyclic sort while reading this problem. Turns out it is the correct solution.

[@user-vy7gk2qn9l]

Amassing solution!!!

[@amrholo4445]

Thanks a lot sir

[@faisalabdulkadir9439]

I really respect u and all the work u do , u have really helped me a lot , pls can the next problem I solve be the increasing in order search tree leetcode 897, I’m finding it hard to grasp the recursion process

[@samuelcordova5183]

please do word pattern II. love your videos

[@vdyb745]

Superb !!!

[@amanrai5285]

I had a hard time to understand the problem:
My way of understanding is:
We are using the indexes to our advantage as they are in range of n. So we are marking the values at the indexes as -ve to signify(the number in the array) is marked visited by putting a -ve sign on the particular index. Finally we loop through all the elements and find which indexes are not -ve and then return them.

[@balajipattabhiraman]

Could we sort and see if the index value and the actual value align and if not detect missing value and update an offset on what the next index would contain if there is no next missing value

[@venkatasundararaman]

Instead of changing them to negative, we can just move the numbers to their index and then finally run a loop to check if the number value at an index is index+1 if not then add that to our result.

[@shaikfaiz593]

Great one

[@RituSharma-zp7xs]

if you move them to their respective index, you will overwrite some of the numbers which we will visit in the future. This could lead to an incorrect response.

[@frida8519]

@@RituSharma-zp7xs you would be swapping numbers, not necessarily overwriting them

[@sk_4142]

@@frida8519 If you swap the numbers, that still results in errors because you might skip the number that you swap. You could probably handle that, but you'll end up realizing that it gets messy very quickly compared to Mr NeetCode's solution.

[@frida8519]

@@sk_4142 yea you're right. I tried doing it the other way and it was just all over the place lol.

[@techsavy5669]

Do it with cyclic sort, will be less confusing✌

[@greentea_vsrg]

I feel like doing this in constant space makes it a medium

[@jayeshkaushik2975]

hey, can you please explain the leetcode contest problems?

[@marekglowacki2607]

I've devised following solution, but I'm not sure if it still counts as O(1) memory:
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
nums = [0] + nums
for n in nums:
if nums[abs(n)] > 0:
nums[abs(n)] *= -1

return [i for i,v in enumerate(nums) if v > 0]

[@andreytamelo1183]

Thanks!

[@NeetCode]

Thank you so much again!!!

[@theresilientpianist7114]

goodquestion

[@SoyAudio]

I love you!!!!!!!!

[@cgqqqq]

does this algo have a name? I saw a couple of problems was solved by the same method but none mentioned the name of the method...

[@pranshusharma26]

Can we solve it like, first take the minimum and maximum value present in the given list.Traverse between minimum to maximum value and then return those numbers which are not in given list ???

[@MarsTheProgrammer]

Yes but traversing numbers between min and max will not result in O(n) time.

[@serhattural3168]

If you sort the array first, it works with time complexity O(nlogn)

[@Ryanamahaffey]

@@serhattural3168 nlogn is still worse than just O(n) a with constant space as shown in the video explanation though

[@rukaiyakhan2406]

can you please name this algorithm

[@shubhk33]

is return list(set(range(1,len(nums)+1)) - set(nums)) a better solution?

[@rafay_syed]

That's what I did and I got a higher runtime

[@leeroymlg4692]

it's a good solution but it is not 0(1) memory as you are creating an additional set

[@lilyh4573]

How come when you multiply any positive number with a negative number (like -1) it turns negative? I've been told that's how it works in school.... but no one told me why?!

[@rukna3775]

look up absolute operation

[@thangnguyenduc9969]

i don't even know how can I come up with this optimal solution in an interview.

[@4r4zzz]

fucking hell, this is awesome

[@janekmuric]

That's not O(1) space, it's still O(1)

[@VarunMittal-viralmutant]

A two liner:
valid_set = set(range(1, len(nums) + 1))
return (valid_set - valid_set.intersection(nums))

[@ArquimedesOfficial]

Can u tell us about Time and Space Complexity for this one?...

[@VarunMittal-viralmutant]

@@ArquimedesOfficial Time complexity O(n) and Space complexity O(n) due to the extra valid_set. To elaborate:
Creating a set of entire range - O(n) Time complexity
Finding intersection - O(min(len(s1), len(s2)) which could be O(n) in worst case
Difference - O(n)
Total time complexity: O(n) + O(n) + O(n) = O(n)

[@dumbfailurekms]

ok that's fucking cool