Missing Number - Blind 75 - Leetcode 268 - Python
Vložit
- čas přidán 30. 06. 2024
- 🚀 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. - Věda a technologie
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.
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
should pass you to the next round the moment you mentioned the formula lol...
I know it's maths but his explanation makes sense.
Yep, interviewer just may say: formula is great and valid, now can you solve it without formula?
@@cringemasteralmyrph3757 except its not lol
Really appreciate the fact that you explain multiple solutions. Always interesting to learn them!
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
I used gauss also, but I agree that the way he solved the problem is much more cleaner
(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
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];
}
@@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;
}
I'm glad that math finally kicked in for me, remembering Gauss's formula for sums.
The clearest explanation I've seen on this. Hot stuff. Thanks for your videos, they are the bomb.
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)
This is the best solution.
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
Such a clean and clear solution !!! Awesome !!
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
how will you know which are the missing numbers from the answer?
Thank you for clearing this problem!
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 🙂
because boolean logic is both associative and commutative.
5^(3^5)
5^(5^3) - commutative property
(5^5)^3 - associative property
= 3
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)
Aww. One of the best explanation🔥Thank you so much🖤
Very clear explanation.. Thanks Man.
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
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)"
Doesn't regular sum arguably take O(lg n) space since you need bits scaling logarithmically with the total sum and length?
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
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.
@@triscuit5103 For leetcode Tom's solution works, because the problem states that n will never be bigger than 10000.
@@bobbyd1658 yes
@@triscuit5103 Why did you say "babe"? You're so damn awkward and cringe. Lmfao
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)?
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
Thank You for your work😍😍😍
Excellent explanation
Wow, the XOR solution was so cool.
Thank you a lot sir
result = len(nums)
for i, n in enumerate(nums):
result += i-n
return result
I hate how sometime I just overthink 😤
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.
Question is even easier now! Doesn't have to be O(n) time complexity last time I checked. lol
still has to be O(n)
Everytime, when you say how long or how much memory it's gonna use. How do you know?
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 ?
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
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.
@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
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.
def missingNumber(self, nums: List[int]) -> int:
maxi = 1e5
for i in range(len(nums)):
idx = int(nums[i]%maxi)
if idx
interesting approaches
Thanks!
Hi Huy - thank you so much, I really appreciate it!! 😊
@@NeetCode thank you so much
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. :(
this probably is the smartest way to code this :)
n = len(nums)
res = 0.5*n*(n+1) - sum(nums)
return int(res)
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.
shorter is return (int)((len(nums)*(len(nums)+1))/2)-sum(nums) :)
the javascript one line equivalent:
``` [0,1,3].reduce((prev, elem, idx) => (prev + (idx + 1) - elem) , 0)
```
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
this needs O(n) space
@@simonzouki4570 it is O(n) time and space
@@slayerzerg hb this
res = len(nums) + 1
for i in range(0, res):
if i not in nums:
return i
I still have no idea what is going on but thank you!
function missing_num(arr) {
let x1 , x2
for (let i = 1; i
You can also just get the sum of the array and subtract the sum of the full array using the triangular's numbers formula
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.
return sum([i for i in range(len(nums)+1)])-sum(nums)
🤷♂
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?
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.
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;
};
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
to be honest I did not understand why we initialize our res = len(nums) at the beginning?
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.
@@77794471 I was so confused but tysm for the explanation!
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
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)
@@alejandrodardon7091 i had the same question, thank you! Great explanation
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.
This works better:
x = (set(range(len(nums)+1)).symmetric_difference(nums))
return list(x)[0]
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
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
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)
Can't we just do it by simply iterating 'i' from 0 to n+1 and check if 'i' is present in given array
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
@@ayushraj6525 thanks 👍🏻
@@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
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.
Can I do this:
def missingNumber(self, nums: List[int]) -> int:
return sum(range(len(nums)+1)) - sum(nums)
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
pls teach code in java , it would help a lot thanks :) , love your explanation.
return len(nums)*(len(nums)+1)//2 - sum(nums)
Can we simply do this `return sum(range(len(nums) + 1)) - sum(nums)`
yes, only if the question allows for O(n) extra space, the leet code expects you to solve it in O(1) extra space.
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
s = (n * (n + 1)) // 2
val = sum(nums)
return s - val
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) #
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
By looking at the ranges, 0
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?
@@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
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
num = (sum(range(0, len(nums) + 1)) - sum(nums))
return num
czcams.com/video/WnPLSRLSANE/video.html actually you can sum two arrays in one loop, so it can be O(n) as well
i used simple mathematics
c = len(nums)
d = sum(nums)
f = (c*(c+1))//2 - d
return f
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)
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
i mean the dude sounds exactly like the daily dose of internet guy
one line
class Solution:
def missingNumber(self, nums: List[int]) -> int:
return sum( [_ for _ in range(len(nums)+1) ] ) - sum(nums)
Java
public static int findMissingNumber(int[] arr) {
int ans = 0;
for (int i=0; i
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
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
@@Rahul-wv1qc That is not O(n) time. the i in nums lookup takes O(n) since its a list. Its O(n^2)
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
Wrong Answer!
7 ^ 0 is not the number itself
7^0 is 7 itself
@@tempomiss8530 7^1 is itself
@@chrisbrophy7508 its an XOR
@@chrisbrophy7508 here 7^0 doesn't mean 7 power zero. 7^0 means 7 xor 0. (Atleast in c++)
class Solution {
public int missingNumber(int[] nums) {
int currSum = 0;
int expected = 0;
int n = nums.length;
for(int i = 0;i
public int missingNumber(int[] nums) {
int xor = nums.length;
for(int i=0;i
nums.sort()
for i in range(0,len(nums)):
if i!=nums[i]:
return i
return len(nums)
class Solution:
def missingNumber(self, nums: List[int]) -> int:
f1 = sum(nums)
n = len(nums)
x = n*(n+1)/2
return int(x-f1)