Question

Formatted question description: https://leetcode.ca/all/73.html

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.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

• 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?

Algorithm

To solve this question with O(1) space complexity, we cannot create a new array. Instead, we can use the first row and first column of the original array to record whether each row and column has a 0.

The following steps can be taken:

1. First, scan the first row and first column of the array. If a 0 is found, set the corresponding flag in the first row and first column to true.
2. Next, scan the entire array (excluding the first row and first column). If a 0 is found at position [i][j], assign 0 to the corresponding numbers in the first row and first column, i.e., set [0][j] and [i][0] to 0.
3. Traverse the entire array again (excluding the first row and first column). If [0][j] or [i][0] is 0, assign the current value to 0, i.e., set matrix[i][j] to 0.
4. Finally, update the first row and first column based on the flags in the first row and first column. If the flag in the first row is true, assign 0 to the corresponding numbers in the first row. Similarly, if the flag in the first column is true, assign 0 to the corresponding numbers in the first column.

Code

• 
public class Set_Matrix_Zeroes {

public class Solution {
public void setZeroes(int[][] matrix) {

if (matrix == null || matrix.length == 0) {
return;
}

int m = matrix.length;
int n = matrix[0].length;

// use first row and first column as marker
// first row/col itself 0 or not? use a boolean flag
boolean isFirstRowZero = false;
boolean isFirstColZero = false;

for (int i = 0; i < n; i++) {
if (matrix[0][i] == 0) {
isFirstRowZero = true;
break;
}
}

for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
isFirstColZero = true;
break;
}
}

for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {

matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}

// set 0: rest first, first-row/col last
for (int col = 1; col < n; col++) {
if (matrix[0][col] == 0) {

int i = 1;
while (i < m) {
matrix[i][col] = 0;
i++;
}
}
}
for (int row = 1; row < m; row++) {
if (matrix[row][0] == 0) {

int j = 1;
while (j < n) {
matrix[row][j] = 0;
j++;
}
}
}

if (isFirstRowZero) {
int j = 0;
while (j < n) {
matrix[0][j] = 0;
j++;
}
}
if (isFirstColZero) {
int i = 0;
while (i < m) {
matrix[i][0] = 0;
i++;
}
}
}
}
}

############

class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean[] rows = new boolean[m];
boolean[] cols = new boolean[n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
rows[i] = true;
cols[j] = true;
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (rows[i] || cols[j]) {
matrix[i][j] = 0;
}
}
}
}
}

• // OJ: https://leetcode.com/problems/set-matrix-zeroes/
// Time: O(MN)
// Space: O(M + N)
class Solution {
public:
void setZeroes(vector<vector<int>>& A) {
int M = A.size(), N = A[0].size();
vector<bool> row(M), col(N);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
row[i] = row[i] || A[i][j] == 0;
col[j] = col[j] || A[i][j] == 0;
}
}
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (row[i] || col[j]) A[i][j] = 0;
}
}
}
};

• class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
rows = [0] * m
cols = [0] * n
for i, row in enumerate(matrix):
for j, v in enumerate(row):
if v == 0:
rows[i] = cols[j] = 1
for i in range(m):
for j in range(n):
if rows[i] or cols[j]:
matrix[i][j] = 0

############

class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
colZeroFlag = False
for i in range(0, len(matrix)):
if matrix[i][0] == 0:
colZeroFlag = True
for j in range(1, len(matrix[0])):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0

for i in reversed(range(0, len(matrix))):
for j in reversed(range(1, len(matrix[0]))):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if colZeroFlag:
matrix[i][0] = 0


• func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
rows := make([]bool, m)
cols := make([]bool, n)
for i, row := range matrix {
for j, v := range row {
if v == 0 {
rows[i] = true
cols[j] = true
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if rows[i] || cols[j] {
matrix[i][j] = 0
}
}
}
}

• /**
Do not return anything, modify matrix in-place instead.
*/
function setZeroes(matrix: number[][]): void {
let m = matrix.length,
n = matrix[0].length;
let c0 = false,
r0 = false;
// 遍历第一行
for (let i = 0; i < m; i++) {
if (!matrix[i][0] && !c0) {
c0 = true;
}
}
// 第一列
for (let j = 0; j < n; j++) {
if (!matrix[0][j] && !r0) {
r0 = true;
}
}
// 用第一行、第一列标记全部
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (!matrix[i][j]) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// set
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (!matrix[i][0] || !matrix[0][j]) {
matrix[i][j] = 0;
}
}
}
// set 第一列
if (c0) {
for (let i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
// 第一行
if (r0) {
for (let j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
}


• /**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function (matrix) {
const m = matrix.length;
const n = matrix[0].length;
const rows = new Array(m).fill(false);
const cols = new Array(n).fill(false);
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
rows[i] = true;
cols[j] = true;
}
}
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (rows[i] || cols[j]) {
matrix[i][j] = 0;
}
}
}
};


• public class Solution {
public void SetZeroes(int[][] matrix) {
int m = matrix.Length, n = matrix[0].Length;
bool i0 = matrix[0].Contains(0), j0 = false;
for (int i = 0; i < m; ++i) {
if (matrix[i][0] == 0) {
j0 = true;
break;
}
}
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 (i0) {
for (int j = 0; j < n; ++j) {
matrix[0][j] = 0;
}
}
if (j0) {
for (int i = 0; i < m; ++i) {
matrix[i][0] = 0;
}
}
}
}