Set Matrix Zeroes - Solution & Explanation
Problem Statement
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?
Approach Overview
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.
Approach 1: Approach 1: Using Additional Space
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.
Complexity
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: Approach 2: Using the Matrix Itself
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.
Complexity
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.
Approach 3: Array Mark
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.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Approach 4: Mark in Place
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.
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Set Matrix Zeroes | O(1) Space Approach | Brute - Better - Optimal • take U forward • 985,115 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Set Matrix Zeroes easy or hard?
How to solve Set Matrix Zeroes in O(1) space?
What is the best approach for Set Matrix Zeroes?
What data structure is used in Set Matrix Zeroes?
What is the time complexity of Set Matrix Zeroes?
Set Matrix Zeroes Python or Java solution availability
Is Set Matrix Zeroes asked at Google or Amazon interviews?
Ready to solve this problem?
Practice Set Matrix Zeroes with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor