if i had never seen this problem before, and the interviewer forced me to use O(1) space, i'd cry
toekneema
The best place for visual learners. This channel is going big soon.
raevenbauto
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).
SnapSHORT
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.
AmishaHSomaiya
Search no more, this is by far the best explanation of this question!
haiquanzheng
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!
bilalejaz
at 12:17 aren't you 0'ing out the purple vector which contains info about which rows to zero?
rahulshah
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
priyankachoudhary
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!
rohithjanardhan
There is a typo in line 19. Should be ( if matrix[0][c] == 0 or matrix[r][0] == 0 )
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
AriKariG
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:
DevilaBakrania
Thanks for the explanation, I don't know if I could ever solve problem like these on my own
sarusreyo
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
dusvn
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
kritmok
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)
dadisuperman
anyone come up with O(1) space in 45 mins interview without knowing the problem before
, they deserve to be called "genius"
MinhTran-jgbx
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.
unitycatalog
Great explanation!🚀 would love more matrix and string problems for future videos
bennypham
An alternative: find a 0 element and use its row and column to store the zero/non-zero info.
