Welcome to Subscribe On Youtube
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
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?
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++; } } } } } ############ 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; } } } }