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

goodquestion

ok that's fucking cool

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

can you please name this algorithm

Do it with cyclic sort, will be less confusing✌

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]

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.

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.

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

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?!

Superb !!!

Thanks!

Thanks a lot sir

Amassing solution!!!

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...

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

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

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.

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

please do word pattern II. love your videos

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

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

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

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

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

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!

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!

Keep up the leetcode!

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

hey, can you please explain the leetcode contest problems?

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 ???

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

I love you!!!!!!!!