Set Matrix Zeroes - In-place - Leetcode 73
Vložit
- čas přidán 8. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/set-zero...
0:00 - Drawing O(m*n) Solution
4:20 - Drawing O(m+n) solution
8:25 - Drawing O(1) Soluton
13:05 - Coding O(1) Solution
leetcode 73
This question was identified as a Facebook interview question from here: github.com/xizhengszhang/Leet...
#matrix #neetcode #python - Věda a technologie
🚀 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).
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!
Great explanation!🚀 would love more matrix and string problems for future videos
Great explanation !!! Really easy to understand....💥💥
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 :)
Loved it! Great explanation with great visualization.
Thanks for the explanation, I don't know if I could ever solve problem like these on my own
love your channel, helps me a lot for my preps
anyone come up with O(1) space in 45 mins interview without knowing the problem before
, they deserve to be called "genius"
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!
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!
Thank you, It is just an awesome explanation!
The best explanation on CZcams.
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
very well explained. Thank you!
THANK YOU!!!!!!understood by only this vid.
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:
Excellent explanation!
Learning from a lot of your video, hope i can find a good software job through these awesome explanations.
Thanks for the explanation. This was crisp explanation.
Thanks for sharing! 💯
Best ever explanation tysm neetcode:)
Great video!
There is a typo in line 19. Should be ( if matrix[0][c] == 0 or matrix[r][0] == 0 )
I was thinking like is O(1) even possible. But then I finally decided to watch the solution. It blew off my mind.
An alternative: find a 0 element and use its row and column to store the zero/non-zero info.
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
thankyou legend once again
awesome idea with O(1) memory!
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.
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)
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.
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
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.
I thought since in-place algorithms require constant space complexity then making a copy of the input matrix wouldn't even be allowed?
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 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
amazing
U a God
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
Tricky question, but you are with us.
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.
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.
(correction) line 19: if matrix[0][c].....
can the code work if no 'rowzero' is taken?
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.
شكرا لك كل الحب لك
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.
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
there are a lot of if-conditions in the double loop - moving them out the code would be much faster :-p
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!
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 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
Crazy
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
Not sure why nobody corrected his mistake but line 19 should be: if matrix[0][c] == 0 or matrix[r][0] == 0:
i think this would be faster if you use heap sort
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 😅
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)
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.
the code needs some correction in the 3 rd for loop
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 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
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
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.
"Pretty intuitive"
Bruh. You must have a 150+ IQ to figure it out by yourself in 30 mins
Why I think this code is tedious? I work out a more simplified version
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?
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
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).
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!!
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
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.
you dont have space to store a fking list? man come on.
Pathetic explanation. Worst question
Twas explained well. Thanks :)