• Time:O(mn)
• Space:O(1)

## C++

``````class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
const int m = matrix.size();
const int n = matrix[0].size();
bool shouldFillFirstRow = false;
bool shouldFillFirstCol = false;

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

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

// store the information in the 1st row/col
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;
}

// fill 0s for the matrix except the 1st row/col
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;

// fill 0s for the 1st row if needed
if (shouldFillFirstRow)
for (int j = 0; j < n; ++j)
matrix[0][j] = 0;

// fill 0s for the 1st col if needed
if (shouldFillFirstCol)
for (int i = 0; i < m; ++i)
matrix[i][0] = 0;
}
};
``````

## JAVA

``````class Solution {
public void setZeroes(int[][] matrix) {
final int m = matrix.length;
final int n = matrix[0].length;
boolean shouldFillFirstRow = false;
boolean shouldFillFirstCol = false;

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

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

// store the information in the 1st row/col
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;
}

// fill 0s for the matrix except the 1st row/col
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;

// fill 0s for the 1st row if needed
if (shouldFillFirstRow)
for (int j = 0; j < n; ++j)
matrix[0][j] = 0;

// fill 0s for the 1st col if needed
if (shouldFillFirstCol)
for (int i = 0; i < m; ++i)
matrix[i][0] = 0;
}
}
``````

## Python

``````class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m = len(matrix)
n = len(matrix[0])
shouldFillFirstRow = 0 in matrix[0]
shouldFillFirstCol = 0 in list(zip(*matrix))[0]

# store the information in the 1st row/col
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0

# fill 0s for the matrix except the 1st row/col
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0

# fill 0s for the 1st row if needed
if shouldFillFirstRow:
matrix[0] = [0] * n

# fill 0s for the 1st col if needed
if shouldFillFirstCol:
for row in matrix:
row[0] = 0
``````