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
[ [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.
[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.
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]
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]; } } } };
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); } } }
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
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; } } } } };
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; } } } } }
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] = 0
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
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; } } } };
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; } } } }
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] = 0
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; } } } }