Set Matrix Zeroes
MedPrompt
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.
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]Example 2:
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Constraints:
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1
Follow up:
- A straightforward solution using
O(mn)space is probably a bad idea. - A simple improvement uses
O(m + n)space, but still not the best solution. - Could you devise a constant space solution?
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to use an auxiliary matrix of the same dimensions as the original. We can iterate through the original matrix to find the locations of all the zeros. Then, based on these locations, we modify the auxiliary matrix by setting the corresponding rows and columns to zero. Finally, we copy the contents of the auxiliary matrix back to the original one. This approach is simple to conceptualize but highly inefficient in terms of space.
Algorithm
- Create a new matrix
ansof sizem x nand copy the originalmatrixinto it. - Iterate through the original
matrixfrom(i, j) = (0, 0)to(m-1, n-1). - If
matrix[i][j]is0:- Set all elements in row
iof theansmatrix to0. - Set all elements in column
jof theansmatrix to0.
- Set all elements in row
- After the iteration is complete, copy the
ansmatrix back to the originalmatrix.
Walkthrough
This method avoids the problem of modifying the matrix while iterating over it, which could lead to a chain reaction of zeroing out unintended rows and columns. By using a separate copy, we can safely record all the required changes before applying them.
Here's the breakdown:
- Create a new matrix, let's call it
ans, with the same dimensionsm x nand copy all elements from the originalmatrixinto it. - Iterate through the original
matrixusing nested loops for rowiand columnj. - If you find an element
matrix[i][j]that is0, you then perform two more loops to set the entirei-th row andj-th column of theansmatrix to0. - After the initial iteration over the original matrix is complete, the
ansmatrix holds the desired final state. The last step is to copy theansmatrix back into the originalmatrixto satisfy the in-place requirement.
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; int[][] ans = new int[m][n]; // Create a copy of the original matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { ans[i][j] = matrix[i][j]; } } // Iterate through the original matrix to find zeros for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { // Set the entire row in the 'ans' matrix to 0 for (int k = 0; k < n; k++) { ans[i][k] = 0; } // Set the entire column in the 'ans' matrix to 0 for (int k = 0; k < m; k++) { ans[k][j] = 0; } } } } // Copy the 'ans' matrix back to the original matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { matrix[i][j] = ans[i][j]; } } }}Complexity
Time
O((m*n) * (m+n))
Space
O(m*n)
Trade-offs
Pros
Very simple and easy to understand.
Separates the logic of finding zeros from modifying the matrix, avoiding common pitfalls.
Cons
Extremely high space complexity, making it impractical for large matrices.
Inefficient time complexity, especially for matrices with many zeros.
A significant improvement over the brute-force approach is to use extra space that is proportional to the dimensions of the matrix, rather than its area. We can use two separate arrays, one to mark which rows need to be zeroed and another for the columns. This reduces the space complexity from O(m*n) to O(m+n).
Algorithm
- Initialize a boolean array
row_zeroof sizemandcol_zeroof sizenwithfalse. - Iterate through the matrix from
(i, j) = (0, 0)to(m-1, n-1). - If
matrix[i][j] == 0, setrow_zero[i] = trueandcol_zero[j] = true. - Iterate through the matrix again.
- For each cell
(i, j), ifrow_zero[i]orcol_zero[j]istrue, setmatrix[i][j] = 0.
Walkthrough
The core idea is to make two passes over the matrix.
In the first pass, we iterate through the entire matrix to identify which rows and columns should be converted to zeros. We use a boolean array row_zero of size m and another boolean array col_zero of size n. When we encounter a zero at matrix[i][j], we mark row_zero[i] = true and col_zero[j] = true.
In the second pass, we iterate through the matrix again. For each cell matrix[i][j], we check our marker arrays. If either row_zero[i] or col_zero[j] is true, it means this cell belongs to a row or column that must be zeroed, so we set matrix[i][j] = 0.
This two-pass approach ensures that we make decisions based on the original state of the matrix without letting our modifications interfere with the logic.
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; boolean[] row_zero = new boolean[m]; boolean[] col_zero = new boolean[n]; // First pass: find the zeros and mark the rows and columns for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { row_zero[i] = true; col_zero[j] = true; } } } // Second pass: set the elements to zero based on the markers for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (row_zero[i] || col_zero[j]) { matrix[i][j] = 0; } } } }}Complexity
Time
O(m*n)
Space
O(m+n)
Trade-offs
Pros
Much better space complexity than the brute-force approach.
Efficient time complexity.
The logic is still relatively straightforward.
Cons
Does not meet the O(1) space complexity follow-up challenge.
Uses extra space that could be significant for very large
morn.
The most optimal solution achieves constant space complexity by cleverly using the first row and first column of the matrix itself as storage for the marker information. Since the first row and column will be overwritten, their original zero-status must be stored in separate variables.
Algorithm
- Create a boolean variable
is_col0_zeroand check if any element in the first column is0. If so, set it totrue. - Iterate through the matrix from
i=0tom-1andj=1ton-1. Ifmatrix[i][j] == 0, setmatrix[i][0] = 0andmatrix[0][j] = 0. - Iterate through the matrix from
i=1tom-1andj=1ton-1. Ifmatrix[i][0] == 0ormatrix[0][j] == 0, setmatrix[i][j] = 0. - Check if
matrix[0][0]is0. If it is, set the entire first row to0. - Check if
is_col0_zeroistrue. If it is, set the entire first column to0.
Walkthrough
This approach avoids using any extra space proportional to the matrix size. The first row and first column are repurposed as the row_zero and col_zero marker arrays from the previous approach.
There's a catch: what if the first row or column itself needs to be zeroed? Using matrix[0][0] as a marker for both the first row and first column is ambiguous. To solve this, we use matrix[0][0] to mark the first row and a separate boolean variable, say is_col0_zero, to track the status of the first column.
The algorithm proceeds in these steps:
- First, check if the first column contains any zeros. If it does, set
is_col0_zero = true. - Next, iterate through the rest of the matrix (from the second column onwards). Use the first row and first column as markers. If
matrix[i][j] == 0, setmatrix[i][0] = 0andmatrix[0][j] = 0. - After marking, iterate through the matrix again (from
matrix[1][1]) and update the values. Ifmatrix[i][0] == 0ormatrix[0][j] == 0, setmatrix[i][j] = 0. - Now, handle the first row. If
matrix[0][0] == 0, it means the first row needs to be zeroed out. - Finally, handle the first column. If
is_col0_zerois true, zero out the first column.
The order of these steps is crucial to avoid erasing marker information before it has been used.
class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; boolean isCol0Zero = false; // Step 1: Check if the first column needs to be zeroed for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { isCol0Zero = true; break; } } // Step 2: Use first row and col as markers for the rest of the matrix // Note: We check matrix[0][0] in the inner loop for the first row for (int i = 0; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } // Step 3: Zero out cells based on markers in first row and col // We iterate from the second row/col to not corrupt markers yet for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } // Step 4: Zero out the first row if needed if (matrix[0][0] == 0) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } // Step 5: Zero out the first column if needed if (isCol0Zero) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } }}Complexity
Time
O(m*n)
Space
O(1)
Trade-offs
Pros
Optimal space complexity, as it modifies the matrix in-place without significant extra storage.
Maintains an efficient O(m*n) time complexity.
Cons
The logic is more complex and less intuitive than other approaches.
It's easy to make mistakes with the order of operations, which can lead to incorrect results by erasing markers prematurely.
Solutions
Solution
public class Solution { public void SetZeroes(int[][] matrix) { int m = matrix.Length, n = matrix[0].Length; bool i0 = matrix[0].Contains(0), j0 = false; for (int i = 0; i < m; ++i) { if (matrix[i][0] == 0) { j0 = true; break; } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (i0) { for (int j = 0; j < n; ++j) { matrix[0][j] = 0; } } if (j0) { for (int i = 0; i < m; ++i) { matrix[i][0] = 0; } } }}class Solution {public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean i0 = false, j0 = false; for (int j = 0; j < n; ++j) { if (matrix[0][j] == 0) { i0 = true; break; } } for (int i = 0; i < m; ++i) { if (matrix[i][0] == 0) { j0 = true; break; } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (i0) { for (int j = 0; j < n; ++j) { matrix[0][j] = 0; } } if (j0) { for (int i = 0; i < m; ++i) { matrix[i][0] = 0; } } }}/** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */ var setZeroes = function (matrix) { const m = matrix.length; const n = matrix[0].length; let i0 = matrix[0].some((v) => v == 0); let j0 = false; for (let i = 0; i < m; ++i) { if (matrix[i][0] == 0) { j0 = true; break; } } for (let i = 1; i < m; ++i) { for (let j = 1; j < n; ++j) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for (let i = 1; i < m; ++i) { for (let j = 1; j < n; ++j) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (i0) { for (let j = 0; j < n; ++j) { matrix[0][j] = 0; } } if (j0) { for (let i = 0; i < m; ++i) { matrix[i][0] = 0; } } };class Solution {public: void setZeroes(vector<vector<int>> &matrix) { int m = matrix.size(), n = matrix[0].size(); bool i0 = false, j0 = false; for (int j = 0; j < n; ++j) { if (matrix[0][j] == 0) { i0 = true; break; } } for (int i = 0; i < m; ++i) { if (matrix[i][0] == 0) { j0 = true; break; } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (i0) { for (int j = 0; j < n; ++j) { matrix[0][j] = 0; } } if (j0) { for (int i = 0; i < m; ++i) { matrix[i][0] = 0; } } }};class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: m, n = len(matrix), len(matrix[0]) i0 = any(v == 0 for v in matrix[0]) j0 = any(matrix[i][0] == 0 for i in range(m)) for i in range(1, m): for j in range(1, n): if matrix[i][j] == 0: matrix[i][0] = matrix[0][j] = 0 for i in range(1, m): for j in range(1, n): if matrix[i][0] == 0 or matrix[0][j] == 0: matrix[i][j] = 0 if i0: for j in range(n): matrix[0][j] = 0 if j0: for i in range(m): matrix[i][0] = 0Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.