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

0:00 - Read the problem
0:49 - Drawing Explanation
6:38 - Coding Explanation

leetcode 448

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

[boris---]

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

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

[nikhilchauhan]

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

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

[hussamq]

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

[leetcodeespanol]

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

[OmarChida]

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

[amanrai]

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.

[danielcustduran]

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

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

[marekglowacki]

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]

[faisalabdulkadir]

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

[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

[greentea_vsrg]

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

[samuelcordova]

please do word pattern II. love your videos

[techsavy]

Do it with cyclic sort, will be less confusing✌

[pranshusharma]

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

[setiyakitchen]

class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
int n = nums.length;
for(int i=0;i<n;i++){
int num = Math.abs(nums[i]);
nums[num-1] = -1*Math.abs(nums[num-1]);
}
for(int i=0;i<n;i++){
if(nums[i]>0){
list.add(i+1);
}
}
return list;
}
}

[sohelsayyad]

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 <= length of array ie 3, then only it works... to meet this point, there must be all items sequential till array's length or duplicates to make its length = 3
so correct input can be : [1, 2, 2] or [2, 2, 2] or [1, 1, 3] etc etc ....[1, 2, 3] will return empty [ ].