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 - 1Follow up:
O(mn) space is probably a bad idea.O(m + n) space, but still not the best solution.The key challenge in Set Matrix Zeroes is modifying the matrix so that if any cell is 0, its entire row and column become zero. A straightforward idea is to first scan the matrix and store which rows and columns contain a zero using additional data structures such as sets or arrays. In a second pass, you update the cells belonging to those rows or columns.
However, this approach uses extra space. A more optimized technique uses the first row and first column as markers. During the first traversal, whenever a zero is found, mark its row and column by setting the corresponding cells in the first row and first column to zero. In a later pass, these markers determine which cells should be updated. Careful handling of the first row and column is required because they are reused as storage.
This optimized method achieves O(m × n) time complexity while reducing space usage to O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Row & Column Tracking using Hash Sets/Arrays | O(m × n) | O(m + n) |
| In-place Marking using First Row and Column | O(m × n) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
If any cell of the matrix has a zero we can record its row and column number using additional memory. But if you don't want to use extra memory then you can manipulate the array instead. i.e. simulating exactly what the question says.
Setting cell values to zero on the fly while iterating might lead to discrepancies. What if you use some other integer value as your marker? There is still a better approach for this problem with 0(1) space.
We could have used 2 sets to keep a record of rows/columns which need to be set to zero. But for an O(1) space solution, you can use one of the rows and and one of the columns to keep track of this information.
We can use the first cell of every row and column as a flag. This flag would determine whether a row or column has been set to zero.
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.
1#include <stdio.h>
2#include <stdbool.h>
3
4void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
5 bool row[matrixSize];
6 bool col[*matrixColSize];
7
8 for(int i = 0; i < matrixSize; ++i) row[i] = false;
9 for(int i = 0; i < *matrixColSize; ++i) col[i] = false;
10
11 for (int i = 0; i < matrixSize; ++i) {
12 for (int j = 0; j < *matrixColSize; ++j) {
13 if (matrix[i][j] == 0) {
14 row[i] = true;
15 col[j] = true;
16 }
17 }
18 }
19
20 for (int i = 0; i < matrixSize; ++i) {
21 for (int j = 0; j < *matrixColSize; ++j) {
22 if (row[i] || col[j]) {
23 matrix[i][j] = 0;
24 }
25 }
26 }
27}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.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Set Matrix Zeroes is a common medium-level matrix problem asked in coding interviews at companies like Amazon, Google, and Meta. It tests matrix traversal, in-place modification, and space optimization techniques.
Using the first row and column allows the algorithm to track which rows and columns need to be zeroed without allocating additional memory. This clever reuse of the matrix helps achieve constant extra space while maintaining linear traversal time.
The optimal approach uses the first row and first column of the matrix as markers to record which rows and columns should be set to zero. After marking during the first traversal, a second pass updates the matrix accordingly. This method keeps the time complexity O(m × n) while reducing extra space to O(1).
A simple approach uses arrays or hash sets to store the indices of rows and columns containing zero. However, the most space‑efficient solution avoids extra data structures by reusing the first row and column of the matrix as markers.