Set Matrix Zeroes
How to Solve the “Set Matrix Zeroes” Problem Efficiently
Matrix manipulation problems are common in coding interviews, often testing your ability to work with multidimensional data and optimize space usage.
One such problem is Set Matrix Zeroes, where the goal is to modify the matrix in-place to set entire rows and columns to zero if any element is zero. Let’s explore the problem and its solutions step-by-step.
Problem Statement
You are given an ( m×n ) matrix of integers, matrix. If any element in the matrix is 0, set its entire row and column to 0. The update must be performed in-place, meaning you cannot use extra space for another matrix.
- 1 <= matrix.length, matrix[0].length <= 100
- -2^31 <= matrix[i][j] <= (2^31) – 1
Example 1
Input: matrix =
[ [0,1],
[ [1,1] ]
Output:
[ [0,0],
[0,1] ]
[ [0,1],
[ [1,1] ]
[ [0,0],
[0,1] ]
Explanation:
Explanation:
The range [0, 3] contains the numbers {0, 1, 2, 3}. The number 0 is missing from the array nums.
Example 2
Input: matrix = [
[1,2,3],
[4,0,5],
[6,7,8]
]
Output: [
[1,0,3],
[0,0,0],
[6,0,8]
]
[1,2,3],
[4,0,5],
[6,7,8]
]
Output: [
[1,0,3],
[0,0,0],
[6,0,8]
]
Explanation:
The range [0, 2] includes the numbers {0, 1, 2}. The number 1 is missing.
There are mainly three approach to solve this problem –
- Brute Force
- Iteration
- Iteration (Space Optimized)
1. Brute Force
- Time complexity: O(m∗n)
- Space complexity:O(m∗n)
Where m is the number of rows and n is the number of columns.
Python
C++
Java
JavaScript
Python
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
ROWS, COLS = len(matrix), len(matrix[0])
mark = [[matrix[r][c] for c in range(COLS)] for r in range(ROWS)]
for r in range(ROWS):
for c in range(COLS):
if matrix[r][c] == 0:
for col in range(COLS):
mark[r][col] = 0
for row in range(ROWS):
mark[row][c] = 0
for r in range(ROWS):
for c in range(COLS):
matrix[r][c] = mark[r][c]
C++
class Solution {
public:
void setZeroes(vector>& matrix) {
int ROWS = matrix.size(), COLS = matrix[0].size();
vector> mark = matrix;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (matrix[r][c] == 0) {
for (int col = 0; col < COLS; col++) {
mark[r][col] = 0;
}
for (int row = 0; row < ROWS; row++) {
mark[row][c] = 0;
}
}
}
}
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
matrix[r][c] = mark[r][c];
}
}
}
};
Java
public class Solution {
public void setZeroes(int[][] matrix) {
int ROWS = matrix.length, COLS = matrix[0].length;
int[][] mark = new int[ROWS][COLS];
for (int r = 0; r < ROWS; r++) {
System.arraycopy(matrix[r], 0, mark[r], 0, COLS);
}
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (matrix[r][c] == 0) {
for (int col = 0; col < COLS; col++) {
mark[r][col] = 0;
}
for (int row = 0; row < ROWS; row++) {
mark[row][c] = 0;
}
}
}
}
for (int r = 0; r < ROWS; r++) {
System.arraycopy(mark[r], 0, matrix[r], 0, COLS);
}
}
}
JavaScript
class Solution {
/**
* @param {number[][]} matrix
* @return {void}
*/
setZeroes(matrix) {
const ROWS = matrix.length, COLS = matrix[0].length;
const mark = matrix.map(row => [...row]);
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if (matrix[r][c] === 0) {
for (let col = 0; col < COLS; col++) {
mark[r][col] = 0;
}
for (let row = 0; row < ROWS; row++) {
mark[row][c] = 0;
}
}
}
}
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
matrix[r][c] = mark[r][c];
}
}
}
}
2. Iteration
Time & Space Complexity
- Time complexity: O(m∗n)
- Space complexity: O(m+n)
Where m is the number of rows and n is the number of columns.
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
void setZeroes(vector>& matrix) {
int rows = matrix.size(), cols = matrix[0].size();
vector rowZero(rows, false);
vector colZero(cols, false);
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
if (matrix[r][c] == 0) {
rowZero[r] = true;
colZero[c] = true;
}
}
}
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
if (rowZero[r] || colZero[c]) {
matrix[r][c] = 0;
}
}
}
}
};
Java
public class Solution {
public void setZeroes(int[][] matrix) {
int rows = matrix.length, cols = matrix[0].length;
boolean[] rowZero = new boolean[rows];
boolean[] colZero = new boolean[cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (matrix[r][c] == 0) {
rowZero[r] = true;
colZero[c] = true;
}
}
}
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (rowZero[r] || colZero[c]) {
matrix[r][c] = 0;
}
}
}
}
}
Python
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
ROWS, COLS = len(matrix), len(matrix[0])
rows, cols = [False] * ROWS, [False] * COLS
for r in range(ROWS):
for c in range(COLS):
if matrix[r][c] == 0:
rows[r] = True
cols[c] = True
for r in range(ROWS):
for c in range(COLS):
if rows[r] or cols[c]:
matrix[r][c] = 0JavaScript
class Solution {
/**
* @param {number[][]} matrix
* @return {void}
*/
setZeroes(matrix) {
const rows = matrix.length, cols = matrix[0].length;
const rowZero = Array(rows).fill(false);
const colZero = Array(cols).fill(false);
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (matrix[r][c] === 0) {
rowZero[r] = true;
colZero[c] = true;
}
}
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (rowZero[r] || colZero[c]) {
matrix[r][c] = 0;
}
}
}
}
}3. Fast And Slow Pointers – II
- Time complexity: O(m∗n)
- Space complexity: O(1)
Where m is the number of rows and n is the number of columns.
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
void setZeroes(vector>& matrix) {
int ROWS = matrix.size(), COLS = matrix[0].size();
bool rowZero = false;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (matrix[r][c] == 0) {
matrix[0][c] = 0;
if (r > 0) {
matrix[r][0] = 0;
} else {
rowZero = true;
}
}
}
}
for (int r = 1; r < ROWS; r++) {
for (int c = 1; c < COLS; c++) {
if (matrix[0][c] == 0 || matrix[r][0] == 0) {
matrix[r][c] = 0;
}
}
}
if (matrix[0][0] == 0) {
for (int r = 0; r < ROWS; r++) {
matrix[r][0] = 0;
}
}
if (rowZero) {
for (int c = 0; c < COLS; c++) {
matrix[0][c] = 0;
}
}
}
};
Java
public class Solution {
public void setZeroes(int[][] matrix) {
int ROWS = matrix.length, COLS = matrix[0].length;
boolean rowZero = false;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (matrix[r][c] == 0) {
matrix[0][c] = 0;
if (r > 0) {
matrix[r][0] = 0;
} else {
rowZero = true;
}
}
}
}
for (int r = 1; r < ROWS; r++) {
for (int c = 1; c < COLS; c++) {
if (matrix[0][c] == 0 || matrix[r][0] == 0) {
matrix[r][c] = 0;
}
}
}
if (matrix[0][0] == 0) {
for (int r = 0; r < ROWS; r++) {
matrix[r][0] = 0;
}
}
if (rowZero) {
for (int c = 0; c < COLS; c++) {
matrix[0][c] = 0;
}
}
}
}
Python
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
ROWS, COLS = len(matrix), len(matrix[0])
rowZero = False
for r in range(ROWS):
for c in range(COLS):
if matrix[r][c] == 0:
matrix[0][c] = 0
if r > 0:
matrix[r][0] = 0
else:
rowZero = True
for r in range(1, ROWS):
for c in range(1, COLS):
if matrix[0][c] == 0 or matrix[r][0] == 0:
matrix[r][c] = 0
if matrix[0][0] == 0:
for r in range(ROWS):
matrix[r][0] = 0
if rowZero:
for c in range(COLS):
matrix[0][c] = 0JavaScript
class Solution {
/**
* @param {number[][]} matrix
* @return {void}
*/
setZeroes(matrix) {
const ROWS = matrix.length;
const COLS = matrix[0].length;
let rowZero = false;
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if (matrix[r][c] == 0) {
matrix[0][c] = 0;
if (r > 0) {
matrix[r][0] = 0;
} else {
rowZero = true;
}
}
}
}
for (let r = 1; r < ROWS; r++) {
for (let c = 1; c < COLS; c++) {
if (matrix[0][c] == 0 || matrix[r][0] == 0) {
matrix[r][c] = 0;
}
}
}
if (matrix[0][0] == 0) {
for (let r = 0; r < ROWS; r++) {
matrix[r][0] = 0;
}
}
if (rowZero) {
for (let c = 0; c < COLS; c++) {
matrix[0][c] = 0;
}
}
}
}
