Dare2Solve
When we find a zero in the matrix, we need to set its entire row and column to zeros. To achieve this in place, we can use the first row and first column of the matrix to store the zero states of the corresponding rows and columns. Additionally, we need two flags to remember if the first row and first column originally contained any zeros.
Initial Setup:
first_row_zero
and first_col_zero
, to check if the first row and the first column need to be zeroed.Mark Rows and Columns:
Set Matrix Elements to Zero:
Zero the First Row and Column:
first_row_zero
and first_col_zero
flags to zero out the first row and column if needed.O(m * n)
O(1)
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
vector<int> row(rows, 0);
vector<int> col(cols, 0);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
row[i] = 1;
col[j] = 1;
}
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (row[i] == 1 || col[j] == 1) {
matrix[i][j] = 0;
}
}
}
}
};
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
rows = len(matrix)
cols = len(matrix[0])
row_set = set()
col_set = set()
for i in range(rows):
for j in range(cols):
if matrix[i][j] == 0:
row_set.add(i)
col_set.add(j)
for i in range(rows):
for j in range(cols):
if i in row_set or j in col_set:
matrix[i][j] = 0
class Solution {
public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean[] row = new boolean[rows];
boolean[] col = new boolean[cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
col[j] = true;
}
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
}
var setZeroes = function(matrix) {
let row = new Array(matrix.length).fill(0)
let col = new Array(matrix[0].length).fill(0)
for(let i=0;i<matrix.length;i++){
for(let j=0;j<matrix[i].length;j++){
if(matrix[i][j]==0){
row[i] = 1
col[j] = 1
} }}
for(let i=0;i<matrix.length;i++){
for(let j=0;j<matrix[i].length;j++){
if(row[i]||col[j]){
matrix[i][j] = 0
}
}
}
return matrix
};