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:
O(mn) space is probably a bad idea.O(m + n) space, but still not the best solution.Problem Overview: Given an m × n matrix, if any element is 0, you must set its entire row and column to 0. The tricky part is doing this without accidentally spreading zeros while scanning the matrix.
Approach 1: Using Additional Space (O(mn) time, O(m+n) space)
This approach tracks which rows and columns must be zeroed using extra data structures. First iterate through the matrix and record indices of rows and columns containing a zero. A set or boolean array works well for this. During a second pass, check whether row i or column j was marked and update matrix[i][j] to zero accordingly. The key idea is separating the detection phase from the update phase so newly written zeros don’t affect the scan. This solution is easy to reason about and commonly used when memory constraints are not strict. The full scan gives O(mn) time complexity and the extra row/column markers require O(m+n) space.
This method relies heavily on sequential traversal of the matrix and efficient membership checks. Using hash-based sets for row and column indices keeps lookup operations constant time. The logic is straightforward and makes a good baseline solution when solving array and grid-based interview problems.
Approach 2: Using the Matrix Itself (O(mn) time, O(1) space)
The optimal solution removes the need for extra storage by using the first row and first column of the matrix as markers. During the first pass, when a zero appears at matrix[i][j], mark the row and column by setting matrix[i][0] and matrix[0][j] to zero. Because the first row and column are reused as markers, track whether they originally contained zeros using two boolean flags. In a second pass, iterate through the inner matrix and zero out cells based on the markers stored in the first row and column. Finally update the first row and column if their flags were set.
The key insight is that the matrix already provides enough space to store row/column markers. This reduces the auxiliary memory from O(m+n) to O(1). The algorithm still performs two linear scans of the grid, so the runtime remains O(mn). Problems like this frequently appear in interviews to test whether you can reuse existing memory instead of allocating extra structures such as a hash table.
Recommended for interviews: Interviewers usually expect the in-place marker approach. Starting with the extra-space solution shows clear thinking and correctness. Improving it to reuse the first row and column demonstrates stronger optimization skills and awareness of space complexity constraints.
This approach uses two additional arrays to track the rows and columns that need to be zeroed.
- Traverse the matrix and mark rows and columns that need to be zeroed.
- Then, update the matrix based on the values in these arrays.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(m + n) for the additional arrays.
This approach uses the matrix itself to track zeroes.
- Use the first row and column as markers.
- Traverse the matrix and if an element is zero, mark its row and column.
- Traverse again and set matrix elements to zero based on marked rows and columns.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1) since the algorithm runs in constant space.
We use arrays rows and cols to mark the rows and columns to be cleared.
Then traverse the matrix again, and clear the elements in the rows and columns marked in rows and cols.
The time complexity is O(mtimes n), and the space complexity is O(m+n). Where m and n are the number of rows and columns of the matrix respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
In the first method, we use an additional array to mark the rows and columns to be cleared. In fact, we can also use the first row and first column of the matrix to mark them, without creating an additional array.
Since the first row and the first column are used to mark, their values may change due to the mark, so we need additional variables i0, j0 to mark whether the first row and the first column need to be cleared.
The time complexity is O(mtimes n), and the space complexity is O(1). Where m and n are the number of rows and columns of the matrix respectively.
Python
Java
C++
Go
TypeScript
JavaScript
C#
| Approach | Complexity |
|---|---|
| Approach 1: Using Additional Space | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Space Complexity: O(m + n) for the additional arrays. |
| Approach 2: Using the Matrix Itself | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Space Complexity: O(1) since the algorithm runs in constant space. |
| Array Mark | — |
| Mark in Place | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Additional Space (Row & Column Sets) | O(mn) | O(m+n) | Best for clarity and quick implementation when memory usage is not restricted |
| Using Matrix as Markers (First Row & Column) | O(mn) | O(1) | Preferred interview solution when minimizing extra space is required |
Set Matrix Zeroes | O(1) Space Approach | Brute - Better - Optimal • take U forward • 883,453 views views
Watch 9 more video solutions →Practice Set Matrix Zeroes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor