This is my first Leetcode solution blog :) I know there are a lottttttt of way better solutions out there, but I blog my solutions here to have a better understanding for myself and as a motivating factor for keeping up my consistency in Leetcode. I would be very glad if it helped you too ;)
I solve Leetcode primarily in Python btw.
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
You must do it in place.
This is a medium level LC question. The question states that, we are given a matrix, once we spot a zero at any position, let’s say [i] [j], the entire ith and jth row and column has to be set as zeroes. The following diagram (taken from the leetcode problem link itself) illustrates what are we required to do with our method.
We can represent matrix in python with the help of nested lists. The above matrix would be represented by [[0,1,2,0],[3,4,5,2],[1,3,1,5]].
From the above diagram we can see how zeroes are set and we only update rows and columns as zeroes for the “original” matrix (not the updated one, where we modified the rows and columns to be set to zeroes).
Brute force solution:
My first thought process to this problem was to create a duplicate of the matrix and go through each element of the original matrix and check if the particular element is zero or not. If it is zero, then set the corresponding row and column elements to zero in the duplicate matrix.
But this is not an efficient solution. Since both time and space complexity are O(m*n). (I still have trouble deriving space and time complexity, I have to get it cleared)
Honestly, I was stuck in this problem, so I decided go get help from YouTube (Neetcode). I recommend watching his video, to get a clear understanding. He’s my favorite LC YouTuber :)
O(m+n) space:
O(m+n) space approach involves, taking two extra lists (markers) where you can keep track of which rows and which columns has to be set to zero.
The pink list is used to track the rows and the green to track the columns. As usual, we go through every element in the matrix, if a zero is spotted, the row and column trackers will now keep track of it.
After iterating throughout the matrix, with the help of those marker lists, we now set the original matrix’s to zeroes at required places.
But this can be made more efficient, by using just O(1) space!
How?
O(1) space approach:
Instead of taking two separate marker lists, we embed our markers inside of the matrix, that is our 0th column and 0th row.
Here pink indicates the row marker and green indicates the column marker. As you can see, there is an overlap between the two markers in the first element of the matrix (at [0][0] position).
To counter this problem, we give the first element to the column marker and allocate a separate variable, (let’s say rowMat )for the row marker to indicate if the 0th row has to be set to zero.
We traverse the entire matrix. If zero is found, mark the corresponding rows and column trackers to zero. (Just update the 0th row and 0th columns) For example, if zero is found in [2][1] (2nd row and 1st column) you will set matrix[0][1] and matrix[2][0] to zero. Draw the matrix on your notebook and try to do this step to get a better visualization.
After marking, we once again traverse through the matrix (excluding the 0th row and 0th column, since it was already updated) and set zeroes at each position if zeroes are found in the corresponding positions in row and column markers. We also check the extra boolean variable rowMat , if its true, we make the entire 0th row to zeroes.
Code:
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
r, c = len(matrix), len(matrix[0]) #get the lengths
rowMat = False
#traverse thru each element
for row in range(r):
for col in range(c):
if matrix[row][col] == 0:
if row == 0:
rowMat = True
#we only assign rowMat true when row is in 0th position
else:
matrix[row][0] = 0
matrix[0][col] = 0
#check the row marker
for row in range(1, r):
if matrix[row][0] == 0:
for col in range(1, c):
matrix[row][col] = 0
#check the column marker
for col in range(c):
if matrix[0][col] == 0:
for row in range(r):
matrix[row][col] = 0
#extra variable
if rowMat:
for col in range(c):
matrix[0][col] = 0The matrix is now set to zeroes in place :)
If you still don’t understand or get stuck with the code do use ChatGPT to explain line by line.
Idk, maybe this blog post is too long for a simple problem ahaha
I took a very long time for this problem, I should increase my speed :’)
BTW, I’m open to feedbacks :)
-nyxxie ❤
