Missing Number - Blind 75 - Leetcode 268 - Python

[@supercarpro]

Friggin calculus taught me the sum is just n(n+1)/2 so just loop through array and keep subtracting from that, remaining will be result. Tried using that formula in an interview once and bro was just like "but thats just math" and ignored it lmao. Thanks for the vids, really high quality and I get excited seeing you covered a problem I need help on.

[@cringemasteralmyrph3757]

When i tell you i laughed when you mentioned he said "but that's just math". Like, "Ya, duh. Is this your first time figuring out that programming and algorithms ARE 'just math' ??" lmaooooo

[@NodeBear]

should pass you to the next round the moment you mentioned the formula lol...

[@davidaw104]

I know it's maths but his explanation makes sense.

[@ViktorKishankov]

Yep, interviewer just may say: formula is great and valid, now can you solve it without formula?

[@rukna3775]

@@cringemasteralmyrph3757 except its not lol

[@robogirlTinker]

(Python - XOR) class Solution: def missingNumber(self, nums: List[int]) -> int: res = len(nums) for i in range(len(nums)): res ^= i ^ nums[i] return res

[@samsegalloldude]

Any chance you'll translate that to c++ or c? from what I can tell in the video it's not clear how xor is applied between the shown 2 arrays. EDIT: Figured it out, as I previously thought about XORing each element in the array with the next element. My C code solution for this: int missingNumber(int* nums, int numsSize) { int i = 0; int whole_n_sequence = 0; for (i = 1; i < numsSize; ++i) { nums[i] ^= nums[i - 1]; //Xor each element in nums with the next one whole_n_sequence ^= i; //Xor whole numbers in sequence 0,1,2, ... n. } whole_n_sequence ^= i; //Xor last i (loop starts from i = 1) return whole_n_sequence ^ nums[numsSize-1]; }

[@andytorres1556]

@@samsegalloldude in c++ : int missingNumber(vector& nums) { int res = nums.size(); for(int i = 0; i < nums.size(); i++) { res ^= i^nums[i]; } return res; }

[@aniruddhalappathi4721]

@@samsegalloldude class Solution { int missingNumber(vector& nums): int res = nums.size(); for (unsigned int i = 0; i < nums.size(); i++) { res ^= i ^ nums[i]; } return res; } C++

[@lee_land_y69]

you can also use a closed for of sequence (1 + 2 + ...+ n) and subtract a sum of nums. solution would be len(nums)*(len(nums) + 1) / 2 - sum(nums)

[@xl0xl0xl0]

This is the best solution.

[@jjayguy23]

This is so confusing to me. I've watched it several times. The solution looks simple, but something is throwing me off. What does "res = len(nums)" do?? I don't get why you changed it from 0.

[@nickleo4308]

@77794471 6 months ago (edited) Range function in python just increments and stops at the number. Say you put in 3, the loop will iterate 3 times before stopping. Issue is you'll be left with 0,1,2. So in order to get that last number we just pre initialized res = len(nums), this way we also get the last number for our results.(copied and pasted the above comment) i had the same doubt too lol

[@vishalsinghsengar7951]

I was asked the same question in interview, with a twist that more than 1 number can be missing, with that the sum() logic doesn't work. But the XOR logic will

[@mirrorinfinite5392]

how will you know which are the missing numbers from the answer?

[@servantofthelord8147]

@@mirrorinfinite5392 i'm also curious about this

[@musicgotmelike9668]

Really appreciate the fact that you explain multiple solutions. Always interesting to learn them!

[@codeisawesome369]

Thanks for the upload! I grokked the XOR explanation much better thanks to this as the Leetcode editorial was incomprehensible. Feedback: would've been a bit nicer if the explanation of why 5^3^5 would yield 3 - even though the order is not 5^5^3. I was able to work it out on paper, but the video would be more complete that way 🙂

[@vibhasnaik1234]

because boolean logic is both associative and commutative. 5^(3^5) 5^(5^3) - commutative property (5^5)^3 - associative property = 3

[@tomlee2637]

Can't we just sum the elements in the array and perform subtraction with the expected sum without the number to get the missing element

[@triscuit5103]

Sup babe? Well, in theory, you could. However, you are going to have overflow issues if the numbers are too big. You get what I mean babe? Like, say X is the maximum positive integer your system supports, and say the array has X-1 and X-2, and you add them up, boooooom, it explodes.

[@bobbyd1658]

@@triscuit5103 For leetcode Tom's solution works, because the problem states that n will never be bigger than 10000.

[@nvm3172]

@@bobbyd1658 yes

[@fahid3342]

@@triscuit5103 Why did you say "babe"? You're so damn awkward and cringe. Lmfao

[@trenvert123]

Where in the code is XOR happening? I am confused. Is it res += (i - nums[i])? If so, why does that work? Is it Python exclusive syntax, and I need to figure out what Python is doing under the hood in order to translate it to Java? From what I can see, this should just subtract nums[i] from i and add it to res. I tried implementing this in Java, and ran into the error `local variables referenced from a lambda expression must be final or effectively final`. The solution I found for this is to create a second variable to be final. I'm thinking this makes it impossible to implement this solution in O(1) extra space. But I'll keep trying. Edit: Nevermind. I put the question into ChatGPT, and got a working answer. I'm looking into how it works now. The Answer: int missing = nums.length; for (int i = 0; i < len; i++) { missing ^= i ^ nums[i]; } return missing; I feel that this video was a bit rushed, and the breakdown of how the code is following the logic of your higher level explanation is sort of lacking. Still, thanks for the video.

[@ahmetcemek]

I had a hard time understanding the code he wrote. Here is my one line solution based on the second approach he mentioned: class Solution: def missingNumber(self, nums: List[int]) -> int: return sum(range(0, len(nums) + 1)) - sum(nums)

[@sealwithawkwardness3951]

I'm glad that math finally kicked in for me, remembering Gauss's formula for sums.

[@VibeBlind]

result = len(nums) for i, n in enumerate(nums): result += i-n return result

[@Blairyayaya]

Everytime, when you say how long or how much memory it's gonna use. How do you know?

[@codewithshirhaan8494]

2 lines O(n) solution var missingNumber = function(nums) { let sum = nums.reduce((sum,num)=>sum+num); return ((nums.length*(nums.length+1))/2)-sum; };

[@jose.ambrosio]

Your videos are helping me a lot. Thanks, Neetcode! I implemented a simpler solution for this problem with the same time and memory complexity. class Solution: def missingNumber(self, nums: List[int]) -> int: sumAll = 0 for i in range(len(nums) + 1): sumAll += i return sumAll - sum(nums)

[@indraxios]

because of you i am feeling addicted to these problems, now i am sure with some time and practice i will get in Big Tech

[@amarkr1088]

def missingNumber(self, nums: List[int]) -> int: maxi = 1e5 for i in range(len(nums)): idx = int(nums[i]%maxi) if idx

[@mostinho7]

Done thanks Trivial solution: Input array from 0 to n with 1 number only missing, need to figure out what the number is so fullInputSum - actualInputSum gives that element XOR solution When you xor two numbers that are the same output is 0 The order in which you xor numbers doesn’t matter. A xor B xor C same as A xor C xor B So if you xor input with actual array, you are left with the missing number Todo:- check how to xor in Java

[@tenzin8773]

I hate how sometime I just overthink 😤

[@PASTRAMIKick]

I used the Triangular number formula: ((n^2) + n) / 2, for calculating the total sum of the full range and then substracted the sum of the numbers in the given array. Ends up being O(n) for time and O(1) for space

[@AdventureAvenueYT247]

Um so I wrote this code and it cleared all the test cases, can someone tell me why this would not work? class Solution(object): def missingNumber(self, nums): for i in range(len(nums)+1): if i not in nums: return i If there are more numbers could we just not use a list to store it?

[@alejandrodardon7091]

It does work but it would be worst case O(n^2) because each time you check if its not in nums you are essentially going through the entire array again.

[@20c079shakeelakthar]

return sum([i for i in range(len(nums)+1)])-sum(nums) 🤷‍♂

[@Rahul-wv1qc]

class Solution: def missingNumber(self, nums: List[int]) -> int: nums = set(nums) for i in range(len(nums)+1): if i not in nums: return i

[@simonzouki4570]

this needs O(n) space

[@slayerzerg]

@@simonzouki4570 it is O(n) time and space

[@elgizabbasov1963]

​@@slayerzerg hb this res = len(nums) + 1 for i in range(0, res): if i not in nums: return i

[@juliagulia7384]

The way you coded it is so much cleaner, thank you! I was using my handy gauss summation formula but adding and subtracting seems way easier

[@frankl1]

I used gauss also, but I agree that the way he solved the problem is much more cleaner

[@priyam86f]

O(nlogn), const space 5ms Java... sometimes when i cannot come up with O(n) but a solution i design gets accepted, it feels everything is worth it.. class Solution { public int missingNumber(int[] nums) { /*range : 0 to array length */ Arrays.sort(nums); if(nums[0]!=0){ return 0; } for(int i=0;i

[@triscuit5103]

The clearest explanation I've seen on this. Hot stuff. Thanks for your videos, they are the bomb.

[@JumaleAbdi-tu3zh]

Generate a new array from 0 to the length of the array plus one. Add all elements of this new array. Then, add the elements of the given array. Finally, subtract the sum of the first array from the sum of the second array. example code: def missing_num(mylist: list): array_length = len(mylist) + 1 array = list(range(array_length)) return sum(array) - sum(mylist)

[@AndyBnq]

Here is a solution using XOR for those of you who wants a more explicit XOR approach def missingNumber(nums): n = len(nums) xor_all_indices = 0 xor_all_elements = 0 for i in range(n + 1): xor_all_indices ^= i for num in nums: xor_all_elements ^= num return xor_all_indices ^ xor_all_elements

[@MakandalInovasyon]

the javascript one line equivalent: ``` [0,1,3].reduce((prev, elem, idx) => (prev + (idx + 1) - elem) , 0) ```

[@atharvadeshpande6647]

I found out a easy solution but because of sorting it make time complexity o(logn) , Space complextiy remains constant sort(nums.begin(), nums.end()); int count = 0; for(int i=0; i

[@tunglee4349]

I figure out this solution which T.C = O(n) and M.C = O(1) class Solution: def missingNumber(self, nums: List[int]) -> int: n = len(nums) s = n*(n+1)/2 for i in nums: s -= i return int(s) #

[@danny65769]

Can I do this: def missingNumber(self, nums: List[int]) -> int: return sum(range(len(nums)+1)) - sum(nums)

[@abdulsami5843]

and here I was scratching my head trying to find a way to implement binary search on this, I dont know why they put it in that list , can someone explain am I missing something ?

[@montopy6041]

Doesn't regular sum arguably take O(lg n) space since you need bits scaling logarithmically with the total sum and length?

[@IvanRadonjic-j9f]

class Solution(object): def missingNumber(self, nums): """ :type nums: List[int] :rtype: int """ num = (sum(range(0, len(nums) + 1)) - sum(nums)) return num

[@jw-hy4xy]

Is this solution not optimal? sorting the list and then comparing it with its index rearranged = nums.sort() for i in range(len(nums)): if i != nums[i]: return i return i + 1

[@alejandrodardon7091]

Depends what your given programming language's sort function does under the hood, python for example uses quick sort I think which is O(nlogn) as opposed to the methods he used which are O(n)

[@anasofiamartinezaguilar2494]

@@alejandrodardon7091 i had the same question, thank you! Great explanation

[@ahmad3823]

this probably is the smartest way to code this :) n = len(nums) res = 0.5*n*(n+1) - sum(nums) return int(res)

[@triscuit5103]

Sup babe? Well, in theory, you could. However, you are going to have overflow issues if the numbers are too big. You get what I mean babe? Like, say X is the maximum positive integer your system supports, and say the array has X-1 and X-2, and you add them up, boooooom, it explodes.

[@shoham21]

shorter is return (int)((len(nums)*(len(nums)+1))/2)-sum(nums) :)

[@hwang1607]

same solution but I think a little less confusing, sum needs to be sum of [1,n] so just add 1 def missingNumber(self, nums: List[int]) -> int: res = 0 for i in range(len(nums)): res += ((i + 1) - nums[i]) return res

[@nitinraturi]

Here is a O(1) Time and Space complexity solution return ((len(nums) * (len(nums) + 1)) // 2) - sum(nums) # O(1) Explaination: I am calculating the the total size of n natural integers using the formulae (n * (n+1)/2) rather than iterating over nums.

[@cloud-vietnam]

Thanks!

[@NeetCode]

Hi Huy - thank you so much, I really appreciate it!! 😊

[@cloud-vietnam]

@@NeetCode thank you so much

[@bereketyisehak5584]

I got asked this in an interview and used the arithmetic series(math). The interviewer followed up by asking what I would do if two numbers are missing. Why do we keep missing numbers lol? but anyways it went from Coding interview to basically solving a quadratic equation using the sum of squares formula in addition to the arithmetic series. :(

[@hughe29]

This works better: x = (set(range(len(nums)+1)).symmetric_difference(nums)) return list(x)[0]

[@aksedha3861]

class Solution: def missingNumber(self, nums: List[int]) -> int: f1 = sum(nums) n = len(nums) x = n*(n+1)/2 return int(x-f1)

[@Jhundal]

at the start the example about the hash map, wouldn't it be o(n*2) run time instead of O(n) as you will have will need a loop to create the hash map first ?

[@tanvirahmed7993]

Excellent explanation

[@madanmohanpachouly6135]

Very clear explanation.. Thanks Man.

[@rabbyhossain6150]

Bit Manipulation Solution: class Solution: def missingNumber(self, nums: List[int]) -> int: res = len(nums) for i in range(len(nums)): res = res ^ i ^ nums[i] return res

[@jxswxnth]

return len(nums)*(len(nums)+1)//2 - sum(nums)

[@mikhail349u]

kzbin.info/www/bejne/jZ-zfYaIgbh0hKc actually you can sum two arrays in one loop, so it can be O(n) as well

[@lostgoat]

def missingNumber(self, nums: List[int]) -> int: n = len(nums) s = (n * (n + 1)) // 2 val = sum(nums) return s - val

[@MrZackriyaniyas]

def missingNumber(self, nums: List[int]) -> int: n = len(nums) sum = (n * (n+1))//2 for num in nums: sum = sum - num return 0 if sum == 0 else sum using n*(n+1)/2

[@vdyb745]

Such a clean and clear solution !!! Awesome !!

[@KaziMeraj]

I have solved this with the equation. BUT I am trying the codes at the end but that's giving me INCORRECT ANSWER. What am I missing here? NVM, Got it right finally while trying out with pen and paper! Thanks NeetCode

[@iseeflowers]

I love your your clear explanation and videos. I am confused about the part that hash map is O(n) for space/ memory and not O(1)?

[@skyplanet9858]

Thanks for the video. A more general form that can handle any array is this "def missingNumber(array): res_all=0 for i in range(min(array),max(array)): res_all+=i-array[i] return res_all+max(array)"

[@rams2478]

Brilliant explanation... can you please explain this problem also:1060. Missing Element in Sorted Array. I am break my head on Binary search solution for this problem. No matter how many other videos i see im still not getting it. I appreciate your help. Thanks in advance.

[@Joe-oc7lf]

Wrong Answer!

[@shallonp5807]

Wow, the XOR solution was so cool.

[@mikedelta658]

Thank you for clearing this problem!

[@akagamishanks7991]

to be honest I did not understand why we initialize our res = len(nums) at the beginning?

[@77794471]

Range function in python just increments and stops at the number. Say you put in 3, the loop will iterate 3 times before stopping. Issue is you'll be left with 0,1,2. So in order to get that last number we just pre initialized res = len(nums), this way we also get the last number for our results.

[@yasmineelhadi5511]

@@77794471 I was so confused but tysm for the explanation!

[@mohithadiyal6083]

Can't we just do it by simply iterating 'i' from 0 to n+1 and check if 'i' is present in given array

[@ayushraj6525]

Nah because before doing that you have to sort the array which will atleast take O(nlogn) time..But according to the question you have to solve it in o(n) time complexity

[@mohithadiyal6083]

@@ayushraj6525 thanks 👍🏻

[@farjanashaik9601]

@@ayushraj6525 hey! i did it without sorting them time was 3321ms where as for just adding it was 189ms i dont know why is it because of if block may be and the code was: for i in range(len(nums)+1): if i not in nums: return i

[@MichaelShingo]

It's very inefficient because the "in" operator is an O(n) operation. You're doing this every time the loop runs, so your time complexity is O(n^2). If you convert the array to a set() with O(1) lookup time, it helps the time complexity, but now you've used O(n) space.

[@kaiserkonok]

Aww. One of the best explanation🔥Thank you so much🖤

[@LOLjerel]

I still have no idea what is going on but thank you!

[@shanemarchan658]

function missing_num(arr) { let x1 , x2 for (let i = 1; i

[@rogerthat7190]

interesting approaches

[@deckardbarnes6715]

Question is even easier now! Doesn't have to be O(n) time complexity last time I checked. lol

[@LWeRNeO]

still has to be O(n)

[@jackieli1724]

Thank You for your work😍😍😍

[@saurabhchopra]

Can we simply do this `return sum(range(len(nums) + 1)) - sum(nums)`

[@studiouspanda1999]

yes, only if the question allows for O(n) extra space, the leet code expects you to solve it in O(1) extra space.

[@anubhavbanerjee776]

i used simple mathematics c = len(nums) d = sum(nums) f = (c*(c+1))//2 - d return f

[@amrholo4445]

Thank you a lot sir

[@omose14]

Java public static int findMissingNumber(int[] arr) { int ans = 0; for (int i=0; i

[@jeffreyma567]

By looking at the ranges, 0

[@alejandrodardon7091]

Not too sure on this but wouldn't than be O(n^2)? Because you are essentially checking the whole array each time to see if the given index is in the array?

[@zactamzhermin1434]

@@alejandrodardon7091 yep, O(n^2) time O(1) space if nums is a list; O(n) time O(n) space if nums is first converted to a hashset; both are sub-optimal solutions

[@feDlugo]

You can also just get the sum of the array and subtract the sum of the full array using the triangular's numbers formula

[@triscuit5103]

Sup babe? Well, in theory, you could. However, you are going to have overflow issues if the numbers are too big. You get what I mean babe? Like, say X is the maximum positive integer your system supports, and say the array has X-1 and X-2, and you add them up, boooooom, it explodes.

[@lennyliu9251]

one line class Solution: def missingNumber(self, nums: List[int]) -> int: return sum( [_ for _ in range(len(nums)+1) ] ) - sum(nums)

[@weaponkid1121]

i mean the dude sounds exactly like the daily dose of internet guy

[@user-wf3bp5zu3u]

Solution with generator, in-place addition, and re-use of variable: class Solution: def missingNumber(self, nums: List[int]) -> int: res = len(nums) res += sum(i - nums[i] for i in range(res)) return res

[@aditipateriya9166]

pls teach code in java , it would help a lot thanks :) , love your explanation.

[@tarun___choudhary]

Here something that should work: class Solution: def missingNumber(self, nums: List[int]) -> int: for i in range(0, len(nums)+1): if i not in nums: return i

[@Rahul-wv1qc]

O(n) time. we need to come with a better solution. converting list to a set/dict will make O(1) time and O(n) space

[@AdityaVarmaMudunuri]

@@Rahul-wv1qc That is not O(n) time. the i in nums lookup takes O(n) since its a list. Its O(n^2)

[@deepayubipinchandraninama]

I've used a different approach. I got the maximum value in the list and sorted my list first then, I run the loop till (max val + 1) and checked whether i != nums[nums[i]]. if that's not the case then i += 1and if we get if condition correct, then we return i which is the missing value time - O(n) Space - O(1)

[@ravilkashyap7407]

7 ^ 0 is not the number itself

[@tempomiss8530]

7^0 is 7 itself

[@chrisbrophy7508]

@@tempomiss8530 7^1 is itself

[@saatvik1585]

@@chrisbrophy7508 its an XOR

[@tempomiss8530]

@@chrisbrophy7508 here 7^0 doesn't mean 7 power zero. 7^0 means 7 xor 0. (Atleast in c++)

[@saidbouhtoulba6484]

class Solution { public int missingNumber(int[] nums) { int currSum = 0; int expected = 0; int n = nums.length; for(int i = 0;i

[@ashishkarn9283]

public int missingNumber(int[] nums) { int xor = nums.length; for(int i=0;i

[@krishnavamsi9326]

nums.sort() for i in range(0,len(nums)): if i!=nums[i]: return i return len(nums)