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!

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

@huckleberryfinn8795

3 ай бұрын

Its easy for a senior software engineer 😂

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!

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.

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

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

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

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

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

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

hey, can you please explain the leetcode contest problems?

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

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

Keep up the leetcode!

please do word pattern II. love your videos

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.

Amassing solution!!!

Thanks a lot sir

Superb !!!

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

Do it with cyclic sort, will be less confusing✌

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

2 жыл бұрын

Great one

@RituSharma-zp7xs

2 жыл бұрын

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.

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

2 жыл бұрын

look up absolute operation

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]

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

@rafay_syed

2 жыл бұрын

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

Thanks!

@NeetCode

2 жыл бұрын

Thank you so much again!!!

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

2 жыл бұрын

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

@serhattural3168

2 жыл бұрын

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

@Ryanamahaffey

2 жыл бұрын

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

goodquestion

I love you!!!!!!!!

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

can you please name this algorithm

fucking hell, this is awesome

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

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

@ArquimedesOfficial

2 жыл бұрын

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

@VarunMittal-viralmutant

2 жыл бұрын

@@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)

ok that's fucking cool