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 matrix, if any cell contains 0, you must set its entire row and column to 0. The update must reflect all zero positions from the original matrix, not zeros created during processing.
Approach 1: Using Additional Space (Time: O(m*n), Space: O(m+n))
Scan the matrix once and record which rows and columns contain a zero. Two auxiliary structures work well here: a set (or boolean array) for rows and another for columns. During the first pass, whenever matrix[i][j] == 0, store i in the row set and j in the column set. In the second pass, iterate through the matrix again and set matrix[i][j] = 0 if i exists in the row set or j exists in the column set. This approach is straightforward and easy to reason about. The tradeoff is extra memory proportional to the number of rows and columns. It uses ideas common in hash table lookups and works well when clarity matters more than strict memory limits.
Approach 2: Using the Matrix Itself (Time: O(m*n), Space: O(1))
This approach removes the need for extra storage by using the first row and first column of the matrix as markers. During the first pass, whenever you see a zero at (i, j), mark the row and column by setting matrix[i][0] = 0 and matrix[0][j] = 0. A separate flag tracks whether the first column originally contained a zero, since it overlaps with row markers. After marking, iterate through the matrix (excluding the first row and column). If matrix[i][0] == 0 or matrix[0][j] == 0, set the current cell to zero. Finally, update the first row and first column if their markers indicate they should be cleared.
The key insight is reusing existing space inside the matrix to store metadata. Instead of allocating new arrays, the algorithm treats the first row and column as compact marker storage. This technique appears frequently in array and matrix interview problems where constant extra space is required.
Recommended for interviews: Start by explaining the additional-space approach since it clearly demonstrates the logic of tracking rows and columns. Then move to the in-place marker technique. Interviewers typically expect the O(1) space solution because it shows awareness of memory optimization and careful handling of overlapping markers.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Additional Space (Row and Column Sets) | O(m*n) | O(m+n) | Best for readability and quick implementation when extra memory is acceptable. |
| Using the Matrix Itself (First Row/Column Markers) | O(m*n) | O(1) | Preferred in interviews or memory-constrained scenarios requiring constant extra space. |
Set Matrix Zeroes | O(1) Space Approach | Brute - Better - Optimal • take U forward • 565,289 views views
Watch 9 more video solutions →Practice Set Matrix Zeroes with our built-in code editor and test cases.
Practice on FleetCode