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!
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 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.
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.
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 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.
DON'T READ IF YOU have ALREADY UNDERSTOOD if you are confused/not clear : # you need to have a list of n integers then only it works, that's case scenario. In the example array/list have DUPLICATES .... .you need to have duplicates in the array and your task is to find what numbers are missing, whose position these DUPLICATES have taken. .... if you try array [2,3,7] array it will give out of range issue. because MAXIMUM number in array should be
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
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
Summary: Iterating through the array and marking the value at visited index negative. at the end the values which are not marked negative and its corresponding indicies are the values missing in the array.
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 ???
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
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?!
@@ShaolimMatadorPorco69 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)
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!
Exactly, took me a while to really get what the explanation means.
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.
Great explanation, you never disappoint. Keep up the good work.
Constant space problems are always tricky i got this one in interview 😔. Can you make more videos on solving constant space problems
How did u solve that question ?
Thanks for all your hard work Neetcode! Its great to see you consistently upload videos for us! Keep it up!
Yeah I can go back to McDonald if this is easy question....
Its easy for a senior software engineer 😂
@@huckleberryfinn8795 lol
You taking applications?
@@huckleberryfinn8795 im pretty sure its not if he is not solving leetcode questions regularly :)
I immediately though of cyclic sort while reading this problem. Turns out it is the correct solution.
Best approach
Thanks!
Thank you so much again!!!
class Solution {
public List findDisappearedNumbers(int[] nums) {
List list = new ArrayList();
int n = nums.length;
for(int i=0;i
I never figured out this approach. I solved it using sets but this doesn't meet the constraint of space complexity. Great!!!
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.
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.
Great one
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.
@@RituSharma-zp7xs you would be swapping numbers, not necessarily overwriting them
@@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.
@@sadekjn yea you're right. I tried doing it the other way and it was just all over the place lol.
I feel like doing this in constant space makes it a medium
Do it with cyclic sort, will be less confusing✌
Amassing solution!!!
Keep up the leetcode!
DON'T READ IF YOU have ALREADY UNDERSTOOD
if you are confused/not clear :
# you need to have a list of n integers then only it works, that's case scenario.
In the example array/list have DUPLICATES .... .you need to have duplicates in the array and your task is to find what numbers are missing, whose position these DUPLICATES have taken. ....
if you try array [2,3,7] array it will give out of range issue. because MAXIMUM number in array should be
Superb !!!
Thanks a lot sir
please do word pattern II. love your videos
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
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]
Summary:
Iterating through the array and marking the value at visited index negative.
at the end the values which are not marked negative and its corresponding indicies are the values missing in the array.
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 ???
Yes but traversing numbers between min and max will not result in O(n) time.
If you sort the array first, it works with time complexity O(nlogn)
@@serhattural3168 nlogn is still worse than just O(n) a with constant space as shown in the video explanation though
goodquestion
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
is return list(set(range(1,len(nums)+1)) - set(nums)) a better solution?
That's what I did and I got a higher runtime
it's a good solution but it is not 0(1) memory as you are creating an additional set
i don't even know how can I come up with this optimal solution in an interview.
Awesome
I love you!!!!!!!!
can you please name this algorithm
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...
hey, can you please explain the leetcode contest problems?
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?!
look up absolute operation
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))
Can u tell us about Time and Space Complexity for this one?...
@@ShaolimMatadorPorco69 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)
fucking hell, this is awesome
Hi
ok that's fucking cool