I truly believe you helped me a lot. in my first and second year I use to get fear from these questions and procrastinate myself but sir I started watching your videos . 3months back I got 5 stars in Hackerrank. and I found Leetcode harder so I did watch some of your videos I love your solving skills it also improve my ability also today I did complete my 70th question and I am very happy. You are the best programming teacher I ever have got in my life( I am from India ,sorry forgot to mention that).
Appreciate how the video is updated @15:35 to reflect the correction. It shows this channel is updated to ensure correctness and not left unattended once the video is made and out. Thank you for your systematic approach, videos and code solutions. It helps.
Good catch, thank you for pointing it out! Yes you are correct, in reality we need to SKIP the first column, only after we zero out the rows are we allowed to zero out the first column. The code handles this correctly, but I'm sorry about the confusion the picture drawing causes.
Feels easier like this.... class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: rows = {} cols = {} for i in range(len(matrix)): for j in range(len(matrix[i])): if matrix[i][j] == 0: rows[i] = True cols[j] = True for i in range(len(matrix)): for j in range(len(matrix[i])): if i in rows or j in cols: matrix[i][j] = 0 return matrix
The step where you zero out the columns and rows, can be simplified if you visit the matrix in reverse direction, i.e. starting from bottom right. This way you don't need to handle the special cases. Thanks a lot for your videos! They have helped me a lot!
@@joya9785 The reason why we have to zero the first row and col last is because they store zero info. By setting zeros from the bottom right corner, the first col and row will be set to zero last.
@@sidharthamohapatra6950 Actually it will. I think you are talking about missing the last if statement for rowZero. But you have to keep it no matter what kind of zero technique you adopt.
Why would you ask such questions in interviews ? Who is writing such unmaintainable unintuitive production code on a daily basis ? This is like hiring a car mechanic based on his ability to solve algebra.
just adding a little improvement to a great solution, if we use two booleans to keep track of first element of first row and first element of first column then we don't overwrite the first element if it's non zero
Below is the solution for the second approach (use two extra rows): class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: row = [1] * len(matrix) col = [1] * len(matrix[0]) for r in range(len(matrix)): for c in range(len(matrix[0])): if matrix[r][c] == 0: row[r] = 0 col[c] = 0 for r in range(len(matrix)): for c in range(len(matrix[0])): if row[r] == 0 or col[c] == 0: matrix[r][c] = 0
You could also add a continue statement on line 16 to prevent going through rest of column once 0 is found. Will obviously not make a difference to Big O time ofc!
Small improvement: ######## Zero = False for i in range(rows): p = True for j in range(cols): if mat[i][j] == 0: if i ==0: Zero = True continue mat[0][j]=0 p=False if not p and i: mat[i] = [0]*cols for j in range(cols): if mat[0][j]==0: for i in range(1, rows): mat[i][j]=0 if Zero : mat[0] = [0]*cols ######## You iterate only once,i.e O(n*m), and you zero out the columns only when you need. Space O(1)
@@two697 yeah, changing the content of the first row/col AND having a variable seems a bit hacky. But I'm not sure if this solution is O(n) or O(n(n+m)), because in the worst case for each cell you have to check for the entire column and row
won't work because primarily the matrix has data type int, so the 'T' gets converted into its ASCII value when stored, and since matrix[i][j] has the range of all the int, your solution can be hacked by preparing a test case where matrix[i][j] = ascii value of T, and it will fail.
I cheated by replacing the zeros with nulls, which you can do in javascript, and got a 98th percentile solution. Doesn't work in any lower-level language of course.
Interesting solution. For the last solution with the 2 last if statements, I run through some examples ([[1,1,0], [1,1,1,], [1,0,1]]) and kinda understand why we do the update matrix[0][0] first then rowZero: so that we will not overwrite the 1 with 0 in case we update the first row first then the first col (instead of first col then first row) as in the code in the video. However, I feel like that's not a very strong argument in interview, any suggestion will help! For example, if you flip the order of the 2 last if statement, then the solution will be wrong
The problem is: Value of matrix[i][j] can be anything from INT_MAX to INT_MIN, not necessary just 1s and 0s. So changing into 2 can potentially modify the solution.
if first row is zeroed out first due to that extra memory being 0, it will make 0,0 element also 0 even if it was one which will further make column 1 as zero which is wrong. so always make the row/column with extra memory 0 first if 0,0 element is zero.
Can I just replace the numbers I need to set to zero with a letter or something? That way I can just go back after and if the elem is a letter, I set it to 0.
if rowZero: for c in range(cols): if matrix[0][c] == 0: for r in range(1, rows): matrix[r][c] = 0 else: matrix[0][c] = 0 Your rowZero code was incomplete. Thanks for the solution.
I've set all 0 to * and ran the algorithm to convert all row and col of these * to 0 and then convert * back to 0. not sure if this would be accepted in the interview tho
Alternative solution: find rows and columns where all elements in that line are 1. At the intersection of these lines, there will be a 1. Everywhere else, there will be a 0.
Yeah Great Explanation but I did find the same bug which was pinned by NeetCode. I looked at the explanation and in my opinion I did not understand what the correct solution was. So I tried doing it on my own. with your logic. I just made two variables which recorded if the first row and first column should be zero out. Then I just iterated over the first row and zero out the columns. I also iterated over the first column and zero out the row. Then finally to solve the overlapping problem I checked the two variables and zero out the row and column accordingly. Just wondering if this was inefficeint compared to yours. Once agin amazing solution. I completely understood the gist of it.
Either this is infact a supremely intuitive problem relative to other leetcode mediums, or I'm getting better at this stupid Leetcode thing. My self esteem hopes it's the latter 😅
Your algorithm should be manipulating the cells from the given input (in place). In other words, based on how the answer is structured, you should not be creating a new array in order to return it as an answer. I hope this is clear.
Worth nothing that O (m*n) is the worst case, not an average case of an optimal algorithm - such would first check the cells in the columns and rows which are not yet zeroed, and only if there are any remaining non-zeroed, check if they have some 0's. Because, by nature of the task, if filled randomly, the matrix would become all zeroes most of the time.
The problem statement misunderstands O(m+n) with O(m*n). O(m+n) is impossible. Traversing the whole matrix is O(m*n). The brute force solution would be O(m^2*n + m*n^2).
Pass1 : Go through the entire array if you find 0 - replace all elements of row and col with 2 or some different number than 0,1 Pass2 : replace all elements having 2 to 0 Done
That won't work. He explained this case in the video 1 0 1 1 0 1 1 1 1 If you change the first row to all 2's and the second column to all 2's, how will you know that the other zero even existed?
@@dorondavid4698 replace the current zero with a replacement value but don't replace other zeros sharing it's row and column. R could be a string in python, but in languages which don't allow non integers in the data structure, this algorithm won't work. step 1 1 0 1 1 0 1 1 1 1 step 2 R R R 1 0 1 1 R 1 step 3 R R R R R R 1 R 1 step 4 replace R with 0 0 0 0 0 0 0 1 0 1
class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ row,col=len(matrix),len(matrix[0]) rowZeros=False for r in range(row): for c in range(col): if matrix[r][c]==0: matrix[0][c]=0 if r>0: matrix[r][0]=0 else: rowZeros=True for r in range(1,row): for c in range(1,col): if matrix[0][c]==0 or matrix[0][r]==0: matrix[r][c]=0 if matrix[0][0]==0: for r in range(row): matrix[r][0]=0 if rowZeros: for c in range(col): matrix[0][c]=0
Worst case time complexity always gotta be O(mn) because to find all zeroes you have to check each and every cell. This problem perhaps is all about space optimization from what I understand.
Here is my solution for the inefficient algorithm (using duplicate matrix). But the output is the original one. i dont see why: class Solution: def _set_col_to_zero(self, duplicate,colIndex): for i in range(len(duplicate)): duplicate[i][colIndex] = 0
def _set_row_to_zero(self, duplicate,rowIndex): for j in range(len(duplicate[0])): duplicate[rowIndex][j] = 0
def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ duplicate = copy.deepcopy(matrix)
for row in range(len(matrix)): for col in range(len(matrix[0])): if duplicate[row][col] == 0: self._set_row_to_zero(duplicate,row) self._set_col_to_zero(duplicate,col) return duplicate
What if the first index [0][0] is zero? Will that still be okay 11:08? Why do you give such a bad example? Based on your concept, the entire row will be zeroes, even if it doesn't. The first solution (that doesn't work) also goes from top to bottom, left to right, why doesn't that work then? The logic of your code says one thing, and the logic of your explanation says the other. It doesn't even align.
If you're asking what about 0,0 look at the rowZero flag. If you're asking why the picture explanation doesn't match the code, have a look at the pinned comment. If you're asking why the very first solution doesn't work, have a look at the space complexity of making a copy.
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
In list view, add the sorting order also for difficulty level just like it is there in leetcode.
if i had never seen this problem before, and the interviewer forced me to use O(1) space, i'd cry
"I'll buy you more RAM, just leave me alone!"
😂😂
I was just asked this
I truly believe you helped me a lot. in my first and second year I use to get fear from these questions and procrastinate myself but sir I started watching your videos . 3months back I got 5 stars in Hackerrank. and I found Leetcode harder so I did watch some of your videos I love your solving skills it also improve my ability also today I did complete my 70th question and I am very happy. You are the best programming teacher I ever have got in my life( I am from India ,sorry forgot to mention that).
hey where are you now !?
The best place for visual learners. This channel is going big soon.
Thanks, i appreciate the kind words!
184k subs - you were right.
@@torin755 265k already
@@name_surname_1337639k already.
651k today 😊
Appreciate how the video is updated @15:35 to reflect the correction. It shows this channel is updated to ensure correctness and not left unattended once the video is made and out. Thank you for your systematic approach, videos and code solutions. It helps.
Search no more, this is by far the best explanation of this question!
at 12:17 aren't you 0'ing out the purple vector which contains info about which rows to zero?
Good catch, thank you for pointing it out! Yes you are correct, in reality we need to SKIP the first column, only after we zero out the rows are we allowed to zero out the first column. The code handles this correctly, but I'm sorry about the confusion the picture drawing causes.
@@NeetCode yep i made that comment before getting to the code, the code checks out. Super nice channel btw and thanks for the vids :)
@@NeetCode why don't you code in the more popular java
@@cartooncartel6493 clown
@@cartooncartel6493 I think Nick White codes in Java, I'd suggest looking him up :)
Feels easier like this....
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
rows = {}
cols = {}
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if matrix[i][j] == 0:
rows[i] = True
cols[j] = True
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if i in rows or j in cols:
matrix[i][j] = 0
return matrix
i agree
It's an int list so this isn't technically a valid solution.
The step where you zero out the columns and rows, can be simplified if you visit the matrix in reverse direction, i.e. starting from bottom right. This way you don't need to handle the special cases.
Thanks a lot for your videos! They have helped me a lot!
can you brief it out? I'm hella confused
@@joya9785 The reason why we have to zero the first row and col last is because they store zero info. By setting zeros from the bottom right corner, the first col and row will be set to zero last.
@@wayne4591 i think this won't work for 1D matrix
@@sidharthamohapatra6950 Actually it will. I think you are talking about missing the last if statement for rowZero. But you have to keep it no matter what kind of zero technique you adopt.
Exactly!
Why would you ask such questions in interviews ?
Who is writing such unmaintainable unintuitive production code on a daily basis ?
This is like hiring a car mechanic based on his ability to solve algebra.
There is a typo in line 19. Should be ( if matrix[0][c] == 0 or matrix[r][0] == 0 )
anyone come up with O(1) space in 45 mins interview without knowing the problem before
, they deserve to be called "genius"
just adding a little improvement to a great solution, if we use two booleans to keep track of first element of first row and first element of first column then we don't overwrite the first element if it's non zero
Below is the solution for the second approach (use two extra rows):
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
row = [1] * len(matrix)
col = [1] * len(matrix[0])
for r in range(len(matrix)):
for c in range(len(matrix[0])):
if matrix[r][c] == 0:
row[r] = 0
col[c] = 0
for r in range(len(matrix)):
for c in range(len(matrix[0])):
if row[r] == 0 or col[c] == 0:
matrix[r][c] = 0
You could also add a continue statement on line 16 to prevent going through rest of column once 0 is found. Will obviously not make a difference to Big O time ofc!
Thanks for the explanation, I don't know if I could ever solve problem like these on my own
An alternative: find a 0 element and use its row and column to store the zero/non-zero info.
Thank you so much Neetcode for great explanation and solution! I believe Line 19 is --> if matrix[r][0] == 0 or matrix[0][c] == 0:
Small improvement:
########
Zero = False
for i in range(rows):
p = True
for j in range(cols):
if mat[i][j] == 0:
if i ==0:
Zero = True
continue
mat[0][j]=0
p=False
if not p and i:
mat[i] = [0]*cols
for j in range(cols):
if mat[0][j]==0:
for i in range(1, rows):
mat[i][j]=0
if Zero :
mat[0] = [0]*cols
########
You iterate only once,i.e O(n*m), and you zero out the columns only when you need.
Space O(1)
Great explanation!🚀 would love more matrix and string problems for future videos
What about replacing all the 1 in the same row/col of a 0 with "T" and traverse the matrix a second time replacing "T" with 0?
I had the same idea. I believe it should work
@@two697 yeah, changing the content of the first row/col AND having a variable seems a bit hacky.
But I'm not sure if this solution is O(n) or O(n(n+m)), because in the worst case for each cell you have to check for the entire column and row
won't work because primarily the matrix has data type int, so the 'T' gets converted into its ASCII value when stored, and since matrix[i][j] has the range of all the int, your solution can be hacked by preparing a test case where matrix[i][j] = ascii value of T, and it will fail.
@@sandipandutta8776 yeah but the matrix contains only 1 or 0, so that scenario is to be excluded
I was thinking like is O(1) even possible. But then I finally decided to watch the solution. It blew off my mind.
I thought since in-place algorithms require constant space complexity then making a copy of the input matrix wouldn't even be allowed?
I cheated by replacing the zeros with nulls, which you can do in javascript, and got a 98th percentile solution. Doesn't work in any lower-level language of course.
Great explanation !!! Really easy to understand....💥💥
Interesting solution. For the last solution with the 2 last if statements, I run through some examples ([[1,1,0], [1,1,1,], [1,0,1]]) and kinda understand why we do the update matrix[0][0] first then rowZero: so that we will not overwrite the 1 with 0 in case we update the first row first then the first col (instead of first col then first row) as in the code in the video. However, I feel like that's not a very strong argument in interview, any suggestion will help!
For example, if you flip the order of the 2 last if statement, then the solution will be wrong
agreed!
What is your question exactly? Seems you correctly explained the issue correctly.
do O(mxn) complexity solution for better understanding
How about writing 2 at the places were 1 has to be converted to 0. Then in the second loop, mark all 2 to 0.
that's what I did, seems a solid approach
The problem is: Value of matrix[i][j] can be anything from INT_MAX to INT_MIN, not necessary just 1s and 0s. So changing into 2 can potentially modify the solution.
The best explanation on UA-cam.
Thanks for the explanation. This was crisp explanation.
if first row is zeroed out first due to that extra memory being 0, it will make 0,0 element also 0 even if it was one which will further make column 1 as zero which is wrong. so always make the row/column with extra memory 0 first if 0,0 element is zero.
(correction) line 19: if matrix[0][c].....
love your channel, helps me a lot for my preps
very well explained. Thank you!
Gotta skip first column and start with 2nd column around 12:20th mark as to not 0 out the rows but other than that good description
awesome idea with O(1) memory!
Loved it! Great explanation with great visualization.
Can I just replace the numbers I need to set to zero with a letter or something? That way I can just go back after and if the elem is a letter, I set it to 0.
Tricky question, but you are with us.
if rowZero:
for c in range(cols):
if matrix[0][c] == 0:
for r in range(1, rows):
matrix[r][c] = 0
else:
matrix[0][c] = 0
Your rowZero code was incomplete. Thanks for the solution.
no he was right the first time
if rowZero:
for c in range(COLS):
matrix[0][c] = 0
Learning from a lot of your video, hope i can find a good software job through these awesome explanations.
Code was one bug for below condition
if(matrix[0][r]==0 || matrix[r][0]==0) better used if(matrix[0][c]==0 || matrix[r][0]==0)
Good catch, thanks!
Actually here you ended up confusing me more... 😁
I've set all 0 to * and ran the algorithm to convert all row and col of these * to 0 and then convert * back to 0.
not sure if this would be accepted in the interview tho
Best ever explanation tysm neetcode:)
Alternative solution: find rows and columns where all elements in that line are 1. At the intersection of these lines, there will be a 1. Everywhere else, there will be a 0.
In worst case scenario that would be (m*n) rows and columns which are non zero.
Excellent explanation!
Thanks for sharing! 💯
What sorcery is this?
I cracked my head and I could come up with the O(m+n) solution but I was nowhere close to getting the O(1) solution.
THANK YOU!!!!!!understood by only this vid.
"Pretty intuitive"
Bruh. You must have a 150+ IQ to figure it out by yourself in 30 mins
Thank you, It is just an awesome explanation!
my dumb brain could only come up with the first one. sometimes i question whether i even want to come up with a decent solution
Yeah Great Explanation but I did find the same bug which was pinned by NeetCode. I looked at the explanation and in my opinion I did not understand what the correct solution was. So I tried doing it on my own. with your logic. I just made two variables which recorded if the first row and first column should be zero out. Then I just iterated over the first row and zero out the columns. I also iterated over the first column and zero out the row. Then finally to solve the overlapping problem I checked the two variables and zero out the row and column accordingly. Just wondering if this was inefficeint compared to yours. Once agin amazing solution. I completely understood the gist of it.
This was my solution before seeing NeetCode's solution. It just uses 1 more piece of memory.
this is a fucking irritating question
The O(1) is sooooo annoying and unintuitive to figure out if you've never seen the answer before
This problem literally made me stop leetcoding for like a week because I was so frustrated
@@fwan0697 oh no!! hanging there!!! we got this!!
Great video!
i cheated and uses pythonisms to set non-zero values to float('inf') if they become zeroed, then just do a second pass to turn these to 0
there are a lot of if-conditions in the double loop - moving them out the code would be much faster :-p
i think this would be faster if you use heap sort
Not sure why nobody corrected his mistake but line 19 should be: if matrix[0][c] == 0 or matrix[r][0] == 0:
the code needs some correction in the 3 rd for loop
Either this is infact a supremely intuitive problem relative to other leetcode mediums, or I'm getting better at this stupid Leetcode thing. My self esteem hopes it's the latter 😅
can the code work if no 'rowzero' is taken?
why are you starting at 1, col 1, row? why not start at 0
if you start at 0, you'll zero out the first column and row
thankyou legend once again
a small mistake at line 23 range from(1,rows)
We don't have to return anything for this code?! What does it mean? I didn't get any result by this code!
Your algorithm should be manipulating the cells from the given input (in place). In other words, based on how the answer is structured, you should not be creating a new array in order to return it as an answer. I hope this is clear.
solution 3 space is 1 but it is slower than solution 2. it does 2 additional loop at the end to set up row0 and colum0
Worth nothing that O (m*n) is the worst case, not an average case of an optimal algorithm - such would first check the cells in the columns and rows which are not yet zeroed, and only if there are any remaining non-zeroed, check if they have some 0's.
Because, by nature of the task, if filled randomly, the matrix would become all zeroes most of the time.
Why I think this code is tedious? I work out a more simplified version
U a God
amazing
The problem statement misunderstands O(m+n) with O(m*n). O(m+n) is impossible. Traversing the whole matrix is O(m*n). The brute force solution would be O(m^2*n + m*n^2).
شكرا لك كل الحب لك
Pass1 : Go through the entire array if you find 0 - replace all elements of row and col with 2 or some different number than 0,1
Pass2 : replace all elements having 2 to 0
Done
Using a sentinel (2) like this is equivalent to using extra space, which is slightly against the spirit of the question :)
That won't work.
He explained this case in the video
1 0 1
1 0 1
1 1 1
If you change the first row to all 2's and the second column to all 2's, how will you know that the other zero even existed?
@@dorondavid4698 replace the current zero with a replacement value but don't replace other zeros sharing it's row and column.
R could be a string in python, but in languages which don't allow non integers in the data structure, this algorithm won't work.
step 1
1 0 1
1 0 1
1 1 1
step 2
R R R
1 0 1
1 R 1
step 3
R R R
R R R
1 R 1
step 4 replace R with 0
0 0 0
0 0 0
1 0 1
@@toolworks What would be the time complexity here in the worst case?
Crazy
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
row,col=len(matrix),len(matrix[0])
rowZeros=False
for r in range(row):
for c in range(col):
if matrix[r][c]==0:
matrix[0][c]=0
if r>0:
matrix[r][0]=0
else:
rowZeros=True
for r in range(1,row):
for c in range(1,col):
if matrix[0][c]==0 or matrix[0][r]==0:
matrix[r][c]=0
if matrix[0][0]==0:
for r in range(row):
matrix[r][0]=0
if rowZeros:
for c in range(col):
matrix[0][c]=0
the last solution still has a time complexity of O(m*n), memory is O(1)
Worst case time complexity always gotta be O(mn) because to find all zeroes you have to check each and every cell.
This problem perhaps is all about space optimization from what I understand.
Here is my solution for the inefficient algorithm (using duplicate matrix).
But the output is the original one. i dont see why:
class Solution:
def _set_col_to_zero(self, duplicate,colIndex):
for i in range(len(duplicate)):
duplicate[i][colIndex] = 0
def _set_row_to_zero(self, duplicate,rowIndex):
for j in range(len(duplicate[0])):
duplicate[rowIndex][j] = 0
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
duplicate = copy.deepcopy(matrix)
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if duplicate[row][col] == 0:
self._set_row_to_zero(duplicate,row)
self._set_col_to_zero(duplicate,col)
return duplicate
you dont have space to store a fking list? man come on.
Pathetic explanation. Worst question
What if the first index [0][0] is zero? Will that still be okay 11:08? Why do you give such a bad example? Based on your concept, the entire row will be zeroes, even if it doesn't. The first solution (that doesn't work) also goes from top to bottom, left to right, why doesn't that work then?
The logic of your code says one thing, and the logic of your explanation says the other. It doesn't even align.
Have a look at the variable called rowZero. What is it's purpose?
@@__redacted__ You don't get what I mean, do you?
If you're asking what about 0,0 look at the rowZero flag. If you're asking why the picture explanation doesn't match the code, have a look at the pinned comment. If you're asking why the very first solution doesn't work, have a look at the space complexity of making a copy.
@@__redacted__ I'm asking why he says one thing and then later on says another one.
Have a look at the pinned comment.
Twas explained well. Thanks :)