Algorithm
Problem Name: 73. Set Matrix Zeroes
problem Link: https://leetcode.com/problems/set-matrix-zeroes/
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?
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
void setZeroes_1(int **matrix, int m, int n) {
int *row_flag = (int *)calloc(m, sizeof(int));
int *col_flag = (int *)calloc(n, sizeof(int));
int i, j, ii, jj;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row_flag[i] = 1;
col_flag[j] = 1;
}
}
}
for (j = 0; j < n; j++) {
if (col_flag[j]) {
for (ii = 0; ii < m; ii++) {
matrix[ii][j] = 0;
}
}
}
for (i = 0; i < m; i++) {
if (row_flag[i]) {
for (jj = 0; jj < n; jj++) {
matrix[i][jj] = 0;
}
}
}
}
void setZeroes(int **matrix, int m, int n) {
int first_col_zero, first_row_zero;
first_col_zero = first_row_zero = 0;
int i, j;
/* scan first column */
for (i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
first_col_zero = 1;
break;
}
}
/* scan first row */
for (j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
first_row_zero = 1;
break;
}
}
/* scan the matrix */
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
/* set zeros except first column and first row */
for (i = 1; i < m; i++) {
for (j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
/* set first column and first row to zero */
if (first_col_zero) {
for (i = 0; i < m; i++) matrix[i][0] = 0;
}
if (first_row_zero) {
for (j = 0; j < n; j++) matrix[0][j] = 0;
}
}
int main() {
int m, n, i, j;
m = 5;
n = 4;
int **matrix = (int **)calloc(m, sizeof(int *));
for (i = 0; i < m; i++)
matrix[i] = (int *)calloc(n, sizeof(int));
matrix[0][0] = 0; matrix[0][1] = 0; matrix[0][2] = 0; matrix[0][3] = 5;
matrix[1][0] = 4; matrix[1][1] = 3; matrix[1][2] = 1; matrix[1][3] = 4;
matrix[2][0] = 0; matrix[2][1] = 1; matrix[2][2] = 1; matrix[2][3] = 4;
matrix[3][0] = 1; matrix[3][1] = 2; matrix[3][2] = 1; matrix[3][3] = 3;
matrix[4][0] = 0; matrix[4][1] = 0; matrix[4][2] = 1; matrix[4][3] = 1;
setZeroes(matrix, m, n);
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
return 0;
}
Input
matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output
[[1,0,1],[0,0,0],[1,0,1]]
#2 Code Example with C++ Programming
Code -
C++ Programming
// Top-down
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if(matrix.empty()) return;
int m = matrix.size(), n = matrix[0].size(), col0 = 1;
for(int i = 0; i < m; i++){
if(!matrix[i][0]) col0 = 0;
for(int j = 1; j < n; j++)
if(!matrix[i][j]) matrix[0][j] = matrix[i][0] = 0;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++)
if(!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
if(!col0) matrix[i][0] = 0;
}
for(auto& x: matrix[0]) if(!matrix[0][0]) x = 0;
if(!col0) matrix[0][0] = 0;
}
};
// Bottom-up
class Solution {
public:
void setZeroes(vector < vector<int>>& matrix) {
if(matrix.empty()) return;
int m = matrix.size(), n = matrix[0].size(), col0 = 1;
for(int i = 0; i < m; i++){
if(!matrix[i][0]) col0 = 0;
for(int j = 1; j < n; j++)
if(!matrix[i][j]> matrix[0][j] = matrix[i][0] = 0;
}
for(int i = m - 1; i >= 0; i--){
for(int j = n - 1; j > 0; j--)
if(!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
if(!col0) matrix[i][0] = 0;
}
}
};
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]]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean firstRowZero = false;
boolean firstColZero = false;
for (int i = 0; i < rows; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
for (int i = 0; i < cols; i++) {
if (matrix[0][i] == 0) {
firstRowZero = true;
break;
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for (int i = 1; i < rows; i++) {
if (matrix[i][0] == 0) {
for (int j = 0; j < cols; j++) {
matrix[i][j] = 0;
}
}
}
for (int i = 1; i < cols; i++) {
if (matrix[0][i] == 0) {
for (int j = 0; j < rows; j++) {
matrix[j][i] = 0;
}
}
}
if (firstRowZero) {
for (int i = 0; i < cols; i++) {
matrix[0][i] = 0;
}
}
if (firstColZero) {
for (int i = 0; i < rows; i++) {
matrix[i][0] = 0;
}
}
}
}
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]]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const setZeroes = function(matrix) {
const rows = []
const cols = []
const rowNum = matrix.length
const colNum = matrix[0].length
for(let i = 0; i < rowNum; i++) {
for(let j = 0; j < colNum; j++) {
if(matrix[i][j] === 0) {
rows.push(i)
cols.push(j)
}
}
}
const mrows = rows.filter((el, idx, arr) => arr.indexOf(el) === idx)
const mcols = cols.filter((el, idx, arr) => arr.indexOf(el) === idx)
for(let i = 0; i < mrows.length; i++) {
matrix[mrows[i]] = new Array(colNum).fill(0)
}
for(let j = 0; j < mcols.length; j++) {
for(let k = 0; k < rowNum; k++> {
matrix[k][mcols[j]] = 0
}
}
return matrix
};
Input
matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output
[[1,0,1],[0,0,0],[1,0,1]]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def setZeroes(self, matrix):
m, n, x = len(matrix), len(matrix and matrix[0]), 0
for i in range(m):
for j in range(n):
if i < m - 1 and not matrix[i][j] and matrix[i + 1][j]: matrix[i + 1][j] = None
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if i > 0 and not matrix[i][j] and matrix[i - 1][j]: matrix[i - 1][j] = None
while x < m:
y = 0
while y < n:
if matrix[x][y] == 0: matrix[x], y = [0] * n, n
elif not matrix[x][y]: matrix[x][y] = 0
y += 1
x += 1
Input
matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output
[[1,0,1],[0,0,0],[1,0,1]]
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _073_SetMatrixZeroes
{
public void SetZeroes(int[,] matrix)
{
var rowLength = matrix.GetLength(0);
var columnLenght = matrix.GetLength(1);
var rowZero = new bool[rowLength];
var columnZero = new bool[columnLenght];
int i, j;
for (i = 0; i < rowLength; i++)
for (j = 0; j < columnLenght; j++)
if (matrix[i, j] == 0)
{
rowZero[i] = true;
columnZero[j] = true;
}
for (i = 0; i < rowLength; i++)
for (j = 0; j < columnLenght; j++)
if (rowZero[i] || columnZero[j])
matrix[i, j] = 0;
}
public void SetZeroes_2(int[,] matrix)
{
var rowLength = matrix.GetLength(0);
var columnLenght = matrix.GetLength(1);
var firstRowHasZero = false;
var firstColumnHasZero = false;
int i, j;
for (i = 0; i < rowLength; i++)
if (matrix[i, 0] == 0) { firstColumnHasZero = true; break; }
for (i = 0; i < columnLenght; i++)
if (matrix[0, i] == 0) { firstRowHasZero = true; break; }
for (i = 1; i < rowLength; i++)
for (j = 1; j < columnLenght; j++)
if (matrix[i, j] == 0)
matrix[0, j] = matrix[i, 0] = 0;
for (i = 1; i < rowLength; i++)
for (j = 1; j < columnLenght; j++)
if (matrix[i, 0] == 0 || matrix[0, j] == 0)
matrix[i, j] = 0;
if (firstRowHasZero)
for (i = 0; i < columnLenght; i++)
matrix[0, i] = 0;
if (firstColumnHasZero)
for (i = 0; i < rowLength; i++)
matrix[i, 0] = 0;
}
}
}
Input
matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output
[[1,0,1],[0,0,0],[1,0,1]]