Set Matrix Zeroes - In-place - Leetcode 73

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@krishnendubanerjee8523]

In list view, add the sorting order also for difficulty level just like it is there in leetcode.

[@toekneema]

if i had never seen this problem before, and the interviewer forced me to use O(1) space, i'd cry

[@dorondavid4698]

"I'll buy you more RAM, just leave me alone!"

[@shashwatsingh5129]

😂😂

[@vroomerlifts]

I was just asked this

[@VasuChand-wy7mq]

@@vroomerlifts Same MS guy asked me do it in O(1).

[@vroomerlifts]

​@@VasuChand-wy7mqMorgan Stanley or Microsoft ?

[@raevenbauto1578]

The best place for visual learners. This channel is going big soon.

[@NeetCode]

Thanks, i appreciate the kind words!

[@torin755]

184k subs - you were right.

[@name_surname_1337]

@@torin755 265k already

[@mgnfy-view]

​@@name_surname_1337639k already.

[@mvarma31]

651k today 😊

[@SnapSHORT1]

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).

[@-aadfi-1710]

hey where are you now !?

[@AmishaHSomaiya]

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.

[@haiquanzheng5224]

Search no more, this is by far the best explanation of this question!

[@bilalejaz908]

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]

can you brief it out? I'm hella confused

[@wayne4591]

@@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]

@@wayne4591 i think this won't work for 1D matrix

[@wayne4591]

@@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.

[@horanj.1022]

Exactly!

[@rahulshah6119]

at 12:17 aren't you 0'ing out the purple vector which contains info about which rows to zero?

[@NeetCode]

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.

[@rahulshah6119]

@@NeetCode yep i made that comment before getting to the code, the code checks out. Super nice channel btw and thanks for the vids :)

[@cartooncartel6493]

@@NeetCode why don't you code in the more popular java

[@hargovindsingh7074]

@@cartooncartel6493 clown

[@ShouryanNikam]

@@cartooncartel6493 I think Nick White codes in Java, I'd suggest looking him up :)

[@manoor0858]

for (on+m) we can make vector then put zeros indexes here if size if ever greater tahn n+m then all elements should be zero

[@priyankachoudhary3694]

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

[@MinhTran-jg2bx]

anyone come up with O(1) space in 45 mins interview without knowing the problem before , they deserve to be called "genius"

[@rohithjanardhan4970]

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!

[@bennypham4337]

Great explanation!🚀 would love more matrix and string problems for future videos

[@fatihguven7328]

Good job mate! Your videos are really high quality and helping people a lot!

[@sarusreyo]

Thanks for the explanation, I don't know if I could ever solve problem like these on my own

[@DevilaBakrania]

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:

[@chirayujoshi1189]

I was thinking like is O(1) even possible. But then I finally decided to watch the solution. It blew off my mind.

[@vovamorugin]

There is a typo in line 19. Should be ( if matrix[0][c] == 0 or matrix[r][0] == 0 )

[@AriKariG]

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

[@luiggymacias5735]

i agree

[@DanielLancet]

It's an int list so this isn't technically a valid solution.

[@kvtys]

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.

[@nikhildinesan5259]

Great explanation !!! Really easy to understand....💥💥

[@TheBaljitSingh]

Thanks for you understandable easy vocabulary using in this video.

[@unitycatalog]

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.

[@ygwg6145]

An alternative: find a 0 element and use its row and column to store the zero/non-zero info.

[@Live-hh6li]

The best explanation on KZbin.

[@dusvn1484]

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

[@maruwave5389]

Wouldn't the sets take O(m+n) space?

[@dusvn1484]

@@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

[@ivanh7820]

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

[@arunvishwakarma2779]

Thanks for the explanation. This was crisp explanation.

[@rishikaverma9846]

love your channel, helps me a lot for my preps

[@ryanlin2974]

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.

[@DevChannel-b4i]

Great explanation, thanks!

[@doombringer1810]

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?

[@two697]

I had the same idea. I believe it should work

[@doombringer1810]

@@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

[@sandipandutta8776]

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.

[@doombringer1810]

@@sandipandutta8776 yeah but the matrix contains only 1 or 0, so that scenario is to be excluded

[@leohippochin708]

very well explained. Thank you!

[@akshatsamdani]

Loved it! Great explanation with great visualization.

[@sampannapokhrel]

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

[@MinhNguyen-lz1pg]

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

[@priyankachoudhary3694]

agreed!

[@DavidDLee]

What is your question exactly? Seems you correctly explained the issue correctly.

[@shirish_yt]

this is one of the fewest times when i couldnt understand why he started doing all of that in 16:00 and even at last couldnt quite explain why he did that... after that good explanation, it felt short in the code

[@alexandersmirnov4274]

awesome idea with O(1) memory!

[@amufoodie-ian]

Learning from a lot of your video, hope i can find a good software job through these awesome explanations.

[@dadisuperman3472]

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)

[@kritmok1875]

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

[@Raj10185]

Best ever explanation tysm neetcode:)

[@ThePacemaker45]

I thought since in-place algorithms require constant space complexity then making a copy of the input matrix wouldn't even be allowed?

[@jinbowang8814]

Excellent explanation!

[@b9944236]

Tricky question, but you are with us.

[@Aamir_Mohammad887]

do O(mxn) complexity solution for better understanding

[@asdfasyakitori8514]

Great video!

[@aishwaryaranghar3385]

THANK YOU!!!!!!understood by only this vid.

[@arunks4918]

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.

[@theblackunderflow1842]

that's what I did, seems a solid approach

[@dvtien9548]

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.

[@akhma102]

Thank you, It is just an awesome explanation!

[@atreyhazelhispanic]

(correction) line 19: if matrix[0][c].....

[@Akaash449]

Actually here you ended up confusing me more... 😁

[@manoor0858]

nice explanation thanks

[@SnapSHORT1]

thankyou legend once again

[@illu1na]

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

[@harshitbhatt5875]

Twas explained well. Thanks :)

[@iamstudying389]

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.

[@sunilgadhetharia2926]

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)

[@AkinduDasanayake]

Good catch, thanks!

[@froobly]

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.

[@Nxck2440]

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.

[@nihalbhandary162]

In worst case scenario that would be (m*n) rows and columns which are non zero.

[@JennNgai]

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]]

[@JeiShian]

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.

[@soumyajitchatterjee5822]

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.

[@lucas29476]

This was my solution before seeing NeetCode's solution. It just uses 1 more piece of memory.

[@rishikaverma9846]

can the code work if no 'rowzero' is taken?

[@williamchen4882]

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.

[@mengdizheng1223]

there are a lot of if-conditions in the double loop - moving them out the code would be much faster :-p

[@tomerharari1063]

Not sure why nobody corrected his mistake but line 19 should be: if matrix[0][c] == 0 or matrix[r][0] == 0:

[@parisahajibabaee2893]

We don't have to return anything for this code?! What does it mean? I didn't get any result by this code!

[@ximinas]

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.

[@iamburntout]

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

[@WoWUndad]

i think this would be faster if you use heap sort

[@ErnestoConfused]

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 😅

[@edwardteach2]

U a God

[@JLJConglomeration]

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

[@ajm0o]

شكرا لك كل الحب لك

[@alokkumar-im3od]

the code needs some correction in the 3 rd for loop

[@travislin8914]

why are you starting at 1, col 1, row? why not start at 0

[@yang5843]

if you start at 0, you'll zero out the first column and row

[@johnlocke4695]

"Pretty intuitive" Bruh. You must have a 150+ IQ to figure it out by yourself in 30 mins

[@oxyht]

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.

[@abdul.arif2000]

no he was right the first time if rowZero: for c in range(COLS): matrix[0][c] = 0

[@aishwaryaranghar3385]

amazing

[@sidazhong2019]

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

[@rethickpavan4264]

a small mistake at line 23 range from(1,rows)

[@anjanobalesh8046]

Crazy

[@haoliu2686]

Why I think this code is tedious? I work out a more simplified version

[@AbhikalpUnakal]

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

[@lucas29476]

Using a sentinel (2) like this is equivalent to using extra space, which is slightly against the spirit of the question :)

[@dorondavid4698]

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?

[@toolworks]

@@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

[@parimal7]

@@toolworks What would be the time complexity here in the worst case?

[@bufdud4]

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).

[@abdul.arif2000]

the last solution still has a time complexity of O(m*n), memory is O(1)

[@DarkOceanShark]

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.

[@alonalon8794]

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

[@zr60]

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.

[@__redacted__]

Have a look at the variable called rowZero. What is it's purpose?

[@zr60]

@@__redacted__ You don't get what I mean, do you?

[@__redacted__]

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.

[@zr60]

@@__redacted__ I'm asking why he says one thing and then later on says another one.

[@__redacted__]

Have a look at the pinned comment.

[@amitupadhyay6511]

this is a fucking irritating question

[@symbol767]

The O(1) is sooooo annoying and unintuitive to figure out if you've never seen the answer before

[@fwan0697]

This problem literally made me stop leetcoding for like a week because I was so frustrated

[@ermansahintatar8296]

@@fwan0697 oh no!! hanging there!!! we got this!!

[@I_capture_emotions]

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

[@pekarna]

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.

[@abhishekpitale3545]

you dont have space to store a fking list? man come on.

[@sethusona7401]

Pathetic explanation. Worst question

[@_Kunal_Pawar]

Thanks for sharing! 💯