If you’re preparing for coding interviews, the “Set Matrix Zeroes” problem is a must-know! In this blog, we’ll explain the problem, walk through three solutions (Brute Force, Better, and Optimal), and make everything easy to understand with code comments, dry runs, and clear explanations.
Here’s the [Problem Link] to begin with.
What Does the Problem Say?
You are given an m x n matrix. If any cell in the matrix is 0, you must set its entire row and column to 0. The operation should be done in-place, meaning you should not use extra space for another matrix.
Example 1
Input:matrix = [[1][1][1],[1][1],[1][1][1]]
Output:[[1][1],[0,][1]]
Explanation:
- The cell at position (1,1) is 0.
- So, set the entire row 1 and column 1 to 0.
Example 2
Input:matrix = [[1],,[1,[1]]
Output:[[0,1]]
Brute Force Solution
Intuition and Approach
Let’s solve the problem step by step in the simplest way:
- Find All Zeroes:
Loop through the matrix. When you find a 0, mark its entire row and column to be set to 0 later. But if you set them to 0 immediately, you might overwrite original values, so we need a way to mark them temporarily. - Mark with a Special Value:
We use a special value (like infinity) to mark cells that should become zero, but were not originally zero. This way, we don’t confuse new zeroes with original zeroes. - Convert Marks to Zero:
After marking, loop again and set all marked cells to 0.
This approach is easy to understand but not the most efficient.
Code Implementation
class Solution:
def markInfinity(self, matrix, row, col):
r = len(matrix)
c = len(matrix[0])
# Mark the entire column
for i in range(r):
if matrix[i][col] != 0: # Avoid overwriting original zeros
matrix[i][col] = float("inf")
# Mark the entire row
for j in range(c):
if matrix[row][j] != 0: # Avoid overwriting original zeros
matrix[row][j] = float("inf")
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
r = len(matrix)
c = len(matrix[0])
# First pass: mark cells to be zeroed
for i in range(r):
for j in range(c):
if matrix[i][j] == 0:
self.markInfinity(matrix, i, j)
# Second pass: set marked cells to 0
for i in range(r):
for j in range(c):
if matrix[i][j] == float("inf"):
matrix[i][j] = 0Code Explanation
- We define a helper function
markInfinityto mark all non-zero cells in the target row and column with infinity. - In the first loop, whenever we find a 0, we call
markInfinityto mark its row and column. - In the second loop, we convert all cells marked as infinity to 0.
Dry Run
Input:matrix = [[1][1][1],[1][1],[1][1][1]]
- First pass:
- Find 0 at (1,1). Mark row 1 and column 1 with infinity (except original zeros).
- Matrix after marking:text
[[1, inf, 1], [inf, 0, inf], [1, inf, 1]] - Second pass:
- Change all infinities to 0.
- Final matrix:text
[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
Time and Space Complexity
- Time Complexity: O((m * n) * (m + n))
For each zero, we may mark an entire row and column. - Space Complexity: O(1) (ignoring the use of infinity as a marker)
Conclusion
The brute force approach is simple and easy to understand, but it’s slow for large matrices.
Better Solution
Intuition and Approach
Let’s improve the solution by keeping track of which rows and columns need to be zeroed:
- Track Rows and Columns:
Use two arrays: one for rows and one for columns. If you find a 0 at (i, j), mark row i and column j. - Set Zeroes:
In a second pass, set a cell to 0 if its row or column is marked.
This approach is much faster and uses extra space proportional to the number of rows and columns.
Code Implementation
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
r = len(matrix)
c = len(matrix[0])
rowTrack = [0 for _ in range(r)] # Track which rows to zero
colTrack = [0 for _ in range(c)] # Track which columns to zero
# First pass: mark rows and columns
for i in range(r):
for j in range(c):
if matrix[i][j] == 0:
rowTrack[i] = -1
colTrack[j] = -1
# Second pass: set zeros
for i in range(r):
for j in range(c):
if rowTrack[i] == -1 or colTrack[j] == -1:
matrix[i][j] = 0Code Explanation
- We use two arrays,
rowTrackandcolTrack, to remember which rows and columns should be zeroed. - In the first loop, we mark the rows and columns for each zero found.
- In the second loop, we set a cell to 0 if its row or column is marked.
Dry Run
Input:matrix = [[1][1][1],[1][1],[1,1,][1]]
- First pass:
- Second pass:
- Set all cells in row 1 and column 1 to 0.
- Final matrix:text
[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
Time and Space Complexity
- Time Complexity: O(m * n)
- Space Complexity: O(m + n) (for the two tracking arrays)
Conclusion
This solution is much more efficient and is a good choice for medium-sized matrices.
Optimal Solution
Intuition and Approach
Can we do this with constant extra space? Yes! Here’s how:
- Use Matrix as Markers:
Use the first row and first column of the matrix itself to store markers for which rows and columns should be zeroed. - Handle First Column Separately:
Since the first cell (0,0) is shared by the first row and column, use a separate variable (col0) to track if the first column needs to be zeroed. - Mark and Set Zeroes:
- First pass: mark the first row and column if any cell in that row/column is zero.
- Second pass: zero out cells based on these markers.
- Finally, zero out the first row and column if needed.
Code Implementation
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
r = len(matrix)
c = len(matrix[0])
col0 = 1 # Flag to check if first column needs to be zeroed
# First pass: use first row and column as markers
for i in range(r):
for j in range(c):
if matrix[i][j] == 0:
if j == 0:
col0 = 0 # Mark first column
else:
matrix[0][j] = 0 # Mark column
matrix[i][0] = 0 # Mark row
# Second pass: set zeroes based on markers (skip first row and column)
for i in range(1, r):
for j in range(1, c):
if matrix[0][j] == 0 or matrix[i][0] == 0:
matrix[i][j] = 0
# Zero out first row if needed
for j in range(c - 1, 0, -1):
if matrix[0][0] == 0:
matrix[0][j] = 0
# Zero out first column if needed
for i in range(0, r):
if col0 == 0:
matrix[i][0] = 0Code Explanation
- We use the first row and column as marker arrays to save space.
col0remembers if the first column needs to be zeroed.- In the first pass, we mark the first row and column for any zero found.
- In the second pass, we set cells to 0 if their row or column is marked.
- Finally, we handle the first row and column separately.
Dry Run
Input:matrix = [[1][1][1],[1][1],[1][1][1]]
- First pass:
- Matrix after marking:text
[[1, 0, 1], [0, 0, 1], [1, 1, 1]] - Second pass:
- Set cells to 0 if their row or column is marked.
- Final matrix:text
[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
Time and Space Complexity
- Time Complexity: O(m * n)
- Space Complexity: O(1) (no extra space used except a few variables)
Conclusion
This is the most efficient solution. It uses the matrix itself for marking and only a few variables, making it perfect for interviews or large inputs.
Final Thoughts
The “Set Matrix Zeroes” problem is a classic example of how to optimize your approach step by step. Start with brute force to understand the problem, then use extra space for efficiency, and finally use in-place tricks for the best solution.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
