Problem 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]]
Python Solution
def setZeroes(matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m, n = len(matrix), len(matrix[0])
first_row_has_zero = False
first_col_has_zero = False
# Check if first row has zero
for j in range(n):
if matrix[0][j] == 0:
first_row_has_zero = True
break
# Check if first column has zero
for i in range(m):
if matrix[i][0] == 0:
first_col_has_zero = True
break
# Use first row and column as markers
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
# Set zeros based on markers
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
# Set first row to zero if needed
if first_row_has_zero:
for j in range(n):
matrix[0][j] = 0
# Set first column to zero if needed
if first_col_has_zero:
for i in range(m):
matrix[i][0] = 0Java Solution
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean firstRowHasZero = false;
boolean firstColHasZero = false;
// Check if first row has zero
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowHasZero = true;
break;
}
}
// Check if first column has zero
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColHasZero = true;
break;
}
}
// Use first row and column as markers
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;
}
}
}
// Set zeros based on markers
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;
}
}
}
// Set first row to zero if needed
if (firstRowHasZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// Set first column to zero if needed
if (firstColHasZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}C++ Solution
class Solution {
public:
void setZeroes(vector>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
bool firstRowHasZero = false;
bool firstColHasZero = false;
// Check if first row has zero
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowHasZero = true;
break;
}
}
// Check if first column has zero
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColHasZero = true;
break;
}
}
// Use first row and column as markers
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;
}
}
}
// Set zeros based on markers
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;
}
}
}
// Set first row to zero if needed
if (firstRowHasZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// Set first column to zero if needed
if (firstColHasZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}; JavaScript Solution
/**
* @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;
let firstRowHasZero = false;
let firstColHasZero = false;
// Check if first row has zero
for (let j = 0; j < n; j++) {
if (matrix[0][j] === 0) {
firstRowHasZero = true;
break;
}
}
// Check if first column has zero
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) {
firstColHasZero = true;
break;
}
}
// Use first row and column as markers
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// Set zeros based on markers
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) {
matrix[i][j] = 0;
}
}
}
// Set first row to zero if needed
if (firstRowHasZero) {
for (let j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// Set first column to zero if needed
if (firstColHasZero) {
for (let i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
};C# Solution
public class Solution {
public void SetZeroes(int[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
bool firstRowHasZero = false;
bool firstColHasZero = false;
// Check if first row has zero
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowHasZero = true;
break;
}
}
// Check if first column has zero
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColHasZero = true;
break;
}
}
// Use first row and column as markers
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;
}
}
}
// Set zeros based on markers
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;
}
}
}
// Set first row to zero if needed
if (firstRowHasZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// Set first column to zero if needed
if (firstColHasZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}Complexity Analysis
- Time Complexity: O(m × n) where m and n are the dimensions of the matrix
- Space Complexity: O(1) using the first row and column as markers
Solution Explanation
This solution uses the first row and column as markers to achieve O(1) space complexity:
- Key steps:
- Store state of first row/column
- Use first row/column as markers
- Process rest of matrix
- Handle first row/column last
- Algorithm flow:
- Check first row and column
- Mark zeros in first row/column
- Set zeros based on markers
- Handle first row/column separately
Key points:
- In-place modification
- Constant extra space
- Handle edge cases
- Clear step-by-step process