Description:
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.
Examples:
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]]Solution in Python:
Python
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# Determine the dimensions of the matrix
m, n = len(matrix), len(matrix[0])
# Variables to mark whether the first row and first column should be zeroed
first_row_has_zero = False
first_col_has_zero = False
# Check if the first row has any zeros
for j in range(n):
if matrix[0][j] == 0:
first_row_has_zero = True
break
# Check if the first column has any zeros
for i in range(m):
if matrix[i][0] == 0:
first_col_has_zero = True
break
# Use the first row and first column to mark zeros
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[0][j] = 0
matrix[i][0] = 0
# Zero out cells based on marks in the first row and column
for i in range(1, m):
for j in range(1, n):
if matrix[0][j] == 0 or matrix[i][0] == 0:
matrix[i][j] = 0
# Zero out the first row if needed
if first_row_has_zero:
for j in range(n):
matrix[0][j] = 0
# Zero out the first column if needed
if first_col_has_zero:
for i in range(m):
matrix[i][0] = 0Detailed Comments:
- Matrix Dimensions:
mandnrepresent the number of rows and columns in the matrix.
- Check First Row and Column:
- Variables
first_row_has_zeroandfirst_col_has_zeroare used to check if the first row or first column contains any zeros. This is important because we’ll use the first row and column to mark other rows and columns that should be zeroed out, but we need to remember the original state of the first row and column.
- Variables
- Mark Zeros in First Row and Column:
- We iterate through the matrix starting from the second row and second column. If an element is zero, we set the corresponding element in the first row and first column to zero. This effectively marks the entire row and column for zeroing out.
- Zero Out Marked Cells:
- We iterate again through the matrix starting from the second row and second column. If the corresponding marker in the first row or first column is zero, we set the cell to zero.
- Handle First Row and Column:
- Finally, we check the flags
first_row_has_zeroandfirst_col_has_zeroto determine if the first row or column should be zeroed out.
- Finally, we check the flags
This approach ensures that we modify the matrix in place without using additional space beyond a few variables, thus achieving a constant space solution.
Solution in Javascript:
JavaScript
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
// Determine the dimensions of the matrix
let m = matrix.length;
let n = matrix[0].length;
// Variables to mark whether the first row and first column should be zeroed
let firstRowHasZero = false;
let firstColHasZero = false;
// Check if the first row has any zeros
for (let j = 0; j < n; j++) {
if (matrix[0][j] === 0) {
firstRowHasZero = true;
break;
}
}
// Check if the first column has any zeros
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) {
firstColHasZero = true;
break;
}
}
// Use the first row and first column to mark zeros
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// Zero out cells based on marks in the first row and column
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[0][j] === 0 || matrix[i][0] === 0) {
matrix[i][j] = 0;
}
}
}
// Zero out the first row if needed
if (firstRowHasZero) {
for (let j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// Zero out the first column if needed
if (firstColHasZero) {
for (let i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
};Solution in Java:
Java
class Solution {
public void setZeroes(int[][] matrix) {
// Determine the dimensions of the matrix
int m = matrix.length;
int n = matrix[0].length;
// Variables to mark whether the first row and first column should be zeroed
boolean firstRowHasZero = false;
boolean firstColHasZero = false;
// Check if the first row has any zeros
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowHasZero = true;
break;
}
}
// Check if the first column has any zeros
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColHasZero = true;
break;
}
}
// Use the first row and first column to mark zeros
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;
}
}
}
// Zero out cells based on marks in the first row and column
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[0][j] == 0 || matrix[i][0] == 0) {
matrix[i][j] = 0;
}
}
}
// Zero out the first row if needed
if (firstRowHasZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// Zero out the first column if needed
if (firstColHasZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}Solution in C#:
C#
public class Solution {
public void SetZeroes(int[][] matrix) {
// Determine the dimensions of the matrix
int m = matrix.Length;
int n = matrix[0].Length;
// Variables to mark whether the first row and first column should be zeroed
bool firstRowHasZero = false;
bool firstColHasZero = false;
// Check if the first row has any zeros
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowHasZero = true;
break;
}
}
// Check if the first column has any zeros
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColHasZero = true;
break;
}
}
// Use the first row and first column to mark zeros
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;
}
}
}
// Zero out cells based on marks in the first row and column
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[0][j] == 0 || matrix[i][0] == 0) {
matrix[i][j] = 0;
}
}
}
// Zero out the first row if needed
if (firstRowHasZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// Zero out the first column if needed
if (firstColHasZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}