# Question

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

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Example 1:

Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

Example 2:

Input:
[
[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]
]

Did you use extra space?
A straight forward 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?

@tag-array



# 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++;
}
}
}
}
}

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