Welcome to Subscribe On Youtube
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]
]
click to show follow up.
Follow up:
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:
- 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.
- 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. - 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., setmatrix[i][j]
to 0. - 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