Set Matrix Zeroes
LeetCode #73 · Medium · Arrays · C++ solution with worked-out approach and complexity analysis.
Approach
In-Place Marking Using First Row and Column
Key insight
We need to know which rows and columns to zero, but we can't afford O(m+n) extra space for the follow-up. The first row and column can double as the marker storage — matrix[0][j] = 0 means column j must be zeroed, and matrix[i][0] = 0 means row i must be zeroed. The only complication is that the first row/column themselves might originally contain zeros, so we record that separately in two booleans before reusing them as markers.
Strategy
- 1Scan the first row and first column; record whether each originally
- 2For every inner cell (i >= 1, j >= 1) that is zero, mark matrix[i][0]
- 3Second pass over inner cells: zero out matrix[i][j] if its row marker
- 4Finally, zero the first row and/or first column based on the booleans.
Time
O(m * n)
constant number of passes over the matrix.
Space
O(1)
only two boolean flags beyond the input.
Problem description(from LeetCode)
Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. You must do it in place.
Examples
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.length
- •n == matrix[0].length
- •1 <= m, n <= 200
- •-2^31 <= matrix[i][j] <= 2^31 - 1
Follow-up
Devise a constant space solution.
C++ Solution
solution.cpp
class Solution {
public:
void setZeroes(vector<vector<int>> &matrix) {
int m = matrix.size(), n = matrix[0].size();
bool firstRowZero = false, firstColZero = false;
for (int j = 0; j < n; j++)
if (matrix[0][j] == 0) firstRowZero = true;
for (int i = 0; i < m; i++)
if (matrix[i][0] == 0) firstColZero = true;
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 (firstRowZero)
for (int j = 0; j < n; j++) matrix[0][j] = 0;
if (firstColZero)
for (int i = 0; i < m; i++) matrix[i][0] = 0;
}
};