Write a function to modify an m x n integer matrix matrix directly, such that if any element in the matrix is 0, its entire corresponding row and column are set to 0. This transformation should be done in place, without using any additional data structures for storage.
Input:
matrix = [
[0,2,3],
[4,5,6],
[7,8,9]
]
Output:
[
[0,0,0],
[0,5,6],
[0,8,9]
]
Explanation: Since the element at the first row and first column is 0, set all elements in the first row and first column to 0.
Understanding the Problem
The naive approach would use O(m + n) extra space by storing which rows and columns need to be zeroed in separate sets. But we can do better by using the matrix itself as storage.
Use the Matrix Itself!
Instead of extra arrays, we can use the first row and first column as markers. When we find a zero at [i][j], we mark:
matrix[i][0] = 0 → "row i needs to be zeroed"
matrix[0][j] = 0 → "column j needs to be zeroed"
But there's a catch! If we modify the first row/column while scanning, we'll lose information about whether they originally had zeros. So we save that first.
Walkthrough
Let's trace through matrix = [[1,1,1],[1,0,1],[1,1,1]]:
Step 1: Save first row/column state
Check if the first row or column originally contains any zeros. Save in boolean flags.
Step 2: Mark zeros using first row/column
Scan the inner matrix [1:][1:]. When we find a zero, mark the corresponding first row and first column cells.
Step 3: Zero the inner matrix
Use the markers to zero out cells. If matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0.
Step 4: Handle first row/column
If our saved flags indicate the first row/column originally had zeros, zero them now.
The order is crucial: we must save the first row/column state before using them as markers, and zero them last so we don't corrupt the markers we're reading.
Solution
Visualization
Python
Try these examples:
def setZeroes(matrix):
rows, cols = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
first_col_zero = any(matrix[i][0] == 0 for i in range(rows))
for i in range(1, rows):
for j in range(1, cols):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
for i in range(1, rows):
for j in range(1, cols):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if first_row_zero:
for j in range(cols):
matrix[0][j] = 0
if first_col_zero:
for i in range(rows):
matrix[i][0] = 0
Set Matrix Zeroes - O(1) space solution
0 / 15
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(m × n) We make a constant number of passes through the matrix: once to check first row/column, once to mark, once to zero inner cells, and potentially once each for first row/column.
Space Complexity: O(1) We only use two boolean variables. The first row and column of the matrix itself serve as our markers, requiring no additional space proportional to input size.
Mark as read
Your account is free and you can post anonymously if you choose.
Your account is free and you can post anonymously if you choose.