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.length
n == matrix[0].length
1 <= 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
class Solution {
public void setZeroes(int[][] matrix) {
Set<Integer> zeroRows = new HashSet<Integer>();
Set<Integer> zeroCols = new HashSet<Integer>();
int m = matrix.length, n = matrix[0].length;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (matrix[i][j] == 0){
zeroRows.add(i);
zeroCols.add(j);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (zeroRows.contains(i) || zeroCols.contains(j)) {
matrix[i][j] = 0;
}
}
}
}
}
- code
class Solution:
def setZeroes(self, matrix):
row_zero = set()
col_zero = set()
m, n = len(matrix), len(matrix[0])
for x in range(m):
for y in range(n):
if matrix[x][y] == 0:
row_zero.add(x)
col_zero.add(y)
for x in range(m):
for y in range(n):
if x in row_zero or y in col_zero:
matrix[x][y] = 0
return matrix
- code
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
def setRowToZero(m, rows):
for r_0 in rows:
m[r_0] = [0] * len(m[0])
def setColToZero(m, cols):
for c_0 in cols:
for eachRow in range(len(m)):
m[eachRow][c_0] = 0
rows, cols = set(), set()
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if matrix[i][j] == 0:
rows.add(i)
cols.add(j)
setRowToZero(matrix, rows)
setColToZero(matrix, cols)
- code
class Solution:
def setZeroes(self, matrix):
# First row has zero?
m, n, firstRowHasZero = len(matrix), len(matrix[0]), not all(matrix[0])
# Use first row/column as marker, scan the matrix
for i in range(1, m):
for j in range(n):
if matrix[i][j] == 0:
matrix[0][j] = matrix[i][0] = 0
# Set the zeros
for i in range(1, m):
for j in range(n - 1, -1, -1):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# Set the zeros for the first row
if firstRowHasZero:
matrix[0] = [0] * n