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.
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).
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.
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.
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
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
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)
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.
This is my solution and I think it's very intuitive. Just remeber which rows and cols need to be 0 and set it in next iteration. setRow = set() setCol = set() for r in range(len(matrix)): for c in range(len(matrix[r])): if matrix[r][c]==0: setRow.add(r) setCol.add(c) for r in range(len(matrix)): for c in range(len(matrix[r])): if r in setRow or c in setCol: matrix[r][c]=0
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
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.
What I did is at each 0, i branched out an marked all the non-zero ones as float('-inf') and then afterward just traversed through the whole thing again changing all the -inf to 0
@@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.
Thanks so much for the explanation! I entered the question into Leetcode and got an error, I'm having trouble debugging. Any ideas? class Solution(object): def setZeroes(self, matrix): """ :type matrix: List[List[int]] :rtype: None Do not return anything, modify matrix in-place instead. """ # O(1) ROWS, COLS = len(matrix), len(matrix[0]) rowZero = False # determine which rows/cols need to be zero for r in range(ROWS): for c in range(COLS): if matrix[r][c] == 0: matrix[0][c] = 0 if r > 0: matrix[r][0] = 0 else: rowZero = True for r in range(1, ROWS): for c in range(1, COLS): if matrix[0][r] == 0 or matrix[r][0] == 0: matrix[r][c] = 0 if matrix[0][0] == 0: for r in range(ROWS): matrix[r][0] = 0 if rowZero: for c in range(COLS): matrix[0][c] = 0 Input matrix = [[1,1,1],[1,0,1],[1,1,1]] Use Testcase Output [[1,0,1],[0,0,0],[1,1,1]] Expected [[1,0,1],[0,0,0],[1,0,1]]
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.
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.
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.
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.
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
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.
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.
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 😅
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.
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.
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
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).
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
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.
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.
🚀 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
@@vroomerlifts Same MS guy asked me do it in O(1).
@@VasuChand-wy7mqMorgan Stanley or Microsoft ?
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.
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 !?
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 :)
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!
Good job mate! Your videos are really high quality and helping people a lot!
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:
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
Great explanation!🚀 would love more matrix and string problems for future videos
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
Great explanation !!! Really easy to understand....💥💥
Thanks for you understandable easy vocabulary using in this video.
anyone come up with O(1) space in 45 mins interview without knowing the problem before
, they deserve to be called "genius"
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.
This is the exact same as the O(m+n) space solution he showed. The whole point of the added complexity is to get the O(1) space.
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!
I was thinking like is O(1) even possible. But then I finally decided to watch the solution. It blew off my mind.
Thanks for the explanation, I don't know if I could ever solve problem like these on my own
There is a typo in line 19. Should be ( if matrix[0][c] == 0 or matrix[r][0] == 0 )
The best explanation on UA-cam.
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)
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.
Great explanation, thanks!
Thanks for the explanation. This was crisp explanation.
love your channel, helps me a lot for my preps
This is my solution and I think it's very intuitive.
Just remeber which rows and cols need to be 0 and set it in next iteration.
setRow = set()
setCol = set()
for r in range(len(matrix)):
for c in range(len(matrix[r])):
if matrix[r][c]==0:
setRow.add(r)
setCol.add(c)
for r in range(len(matrix)):
for c in range(len(matrix[r])):
if r in setRow or c in setCol:
matrix[r][c]=0
Wouldn't the sets take O(m+n) space?
@@maruwave5389 Yes.In worst case every row have one zero and same for col.And that's m+n.But remember set doesn't contain duplicates
Loved it! Great explanation with great visualization.
An alternative: find a 0 element and use its row and column to store the zero/non-zero info.
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.
very well explained. Thank you!
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.
What I did is at each 0, i branched out an marked all the non-zero ones as float('-inf') and then afterward just traversed through the whole thing again changing all the -inf to 0
Learning from a lot of your video, hope i can find a good software job through these awesome explanations.
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
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!
Best ever explanation tysm neetcode:)
Great video!
I thought since in-place algorithms require constant space complexity then making a copy of the input matrix wouldn't even be allowed?
THANK YOU!!!!!!understood by only this vid.
Excellent explanation!
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, It is just an awesome explanation!
Thanks so much for the explanation! I entered the question into Leetcode and got an error, I'm having trouble debugging. Any ideas?
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
# O(1)
ROWS, COLS = len(matrix), len(matrix[0])
rowZero = False
# determine which rows/cols need to be zero
for r in range(ROWS):
for c in range(COLS):
if matrix[r][c] == 0:
matrix[0][c] = 0
if r > 0:
matrix[r][0] = 0
else:
rowZero = True
for r in range(1, ROWS):
for c in range(1, COLS):
if matrix[0][r] == 0 or matrix[r][0] == 0:
matrix[r][c] = 0
if matrix[0][0] == 0:
for r in range(ROWS):
matrix[r][0] = 0
if rowZero:
for c in range(COLS):
matrix[0][c] = 0
Input
matrix =
[[1,1,1],[1,0,1],[1,1,1]]
Use Testcase
Output
[[1,0,1],[0,0,0],[1,1,1]]
Expected
[[1,0,1],[0,0,0],[1,0,1]]
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.
Tricky question, but you are with us.
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.
do O(mxn) complexity solution for better understanding
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.
Twas explained well. Thanks :)
"Pretty intuitive"
Bruh. You must have a 150+ IQ to figure it out by yourself in 30 mins
thankyou legend once again
(correction) line 19: if matrix[0][c].....
can the code work if no 'rowzero' is taken?
Actually here you ended up confusing me more... 😁
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.
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
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!
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.
Be aware that the order of last two steps can't be changed or you might get a wrong answer. You need to check the first col first.
شكرا لك كل الحب لك
there are a lot of if-conditions in the double loop - moving them out the code would be much faster :-p
U a God
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.
Not sure why nobody corrected his mistake but line 19 should be: if matrix[0][c] == 0 or matrix[r][0] == 0:
amazing
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 😅
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
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
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
the code needs some correction in the 3 rd for loop
i think this would be faster if you use heap sort
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
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
a small mistake at line 23 range from(1,rows)
Crazy
Why I think this code is tedious? I work out a more simplified version
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.
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?
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 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).
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
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!!
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 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.
you dont have space to store a fking list? man come on.
Pathetic explanation. Worst question
Thanks for sharing! 💯