Missing Number - Blind 75 - Leetcode 268 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 SPREADSHEET: docs.google.com/spreadsheets/...
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
Problem Link: neetcode.io/problems/missing-...
0:00 - Read the problem
2:42 - XOR Explanation
8:02 - Sum Explanation
9:20 - Coding Explanation
leetcode 268
This question was identified as a facebook interview question from here: github.com/xizhengszhang/Leet...
#sorted #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

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

[@musicgotmelike9668]

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

[@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; }

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

[@sealwithawkwardness3951]

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

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

[@triscuit5103]

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

[@IndraTags]

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

[@vdyb745]

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

[@mikedelta658]

Thank you for clearing this problem!

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

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

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

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

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

[@madanmohanpachouly6135]

Very clear explanation.. Thanks Man.

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

[@kaiserkonok]

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

[@VibeBlind]

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

[@montopy6041]

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

[@tanvirahmed7993]

Excellent explanation

[@jackieli1724]

Thank You for your work😍😍😍

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

[@amrholo4445]

Thank you a lot sir

[@Blairyayaya]

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

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

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

[@shallonp5807]

Wow, the XOR solution was so cool.

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

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

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

[@tenzin8773]

I hate how sometime I just overthink 😤

[@amarkr1088]

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

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

[@rogerthat7190]

interesting approaches

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

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

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

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

[@cloud-vietnam]

Thanks!

[@NeetCode]

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

[@cloud-vietnam]

@@NeetCode thank you so much

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

[@user-ri6kl8du6t]

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

[@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; };

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

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

[@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. :(

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

[@20c079shakeelakthar]

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

[@hughe29]

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

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

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

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

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

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

[@user-mp5ri8ep4k]

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

[@danny65769]

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

[@lostgoat]

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

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

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

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

[@jxswxnth]

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

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

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

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

[@aditipateriya9166]

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

[@mikhail349u]

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

[@anubhavbanerjee776]

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

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

[@lennyliu9251]

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

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

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

[@Joe-oc7lf]

Wrong Answer!

[@weaponkid1121]

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

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

[@omose14]

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

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

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