Set Matrix Zeroes solution and explanation
Google
Infosys
9 more videos on this problem
Set Matrix Zeroes | O(1) Space Approach | Brute - Better - Optimaltake U forward · 30:07 · 985K views
Set Matrix Zeroes - In-place - Leetcode 73NeetCode · 18:05 · 195K views
Leetcode Set Matrix Zeroes || Intuition + Code + Explanation || O(1) spaceCode with Alisha · 19:26 · 64K views
Set Matrix Zeroes (LeetCode 73) | Full solution 3 different ways with diagrams and visualsNikhil Lohia · 18:00 · 64K views
Set Matrix Zeroes | Multiple Approaches | Leetcode 73 | codestorywithMIKcodestorywithMIK · 36:44 · 21K views
Leetcode | 73. Set Matrix Zeroes | Medium | Java SolutionDeveloper Docs · 6:40 · 5K views
Set Matrix Zeroes | Leetcode 73Techdose · 15:18 · 4K views
Set Matrix Zeroes - LeetCode 73 - Coding Interview QuestionsOne Code Man · 5:03 · 3K views
SET MATRIX ZEROS | LEETCODE # 73 | DFS SOLUTIONCracking FAANG · 14:39 · 2K views
Set Matrix Zeroes - LeetCode 73 - JavaScriptAlgoJS · 4:45 · 1K views
The problem
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.lengthn == matrix[0].length1 <= 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?
Approach overview
Problem Overview: Given an m × n matrix, if any element is 0, you must set its entire row and column to 0. The tricky part is doing this without accidentally spreading zeros while scanning the matrix.
Approach 1: Using Additional Space (O(mn) time, O(m+n) space)
This approach tracks which rows and columns must be zeroed using extra data structures. First iterate through the matrix and record indices of rows and columns containing a zero. A set or boolean array works well for this. During a second pass, check whether row i or column j was marked and update matrix[i][j] to zero accordingly. The key idea is separating the detection phase from the update phase so newly written zeros don’t affect the scan. This solution is easy to reason about and commonly used when memory constraints are not strict. The full scan gives O(mn) time complexity and the extra row/column markers require O(m+n) space.
This method relies heavily on sequential traversal of the matrix and efficient membership checks. Using hash-based sets for row and column indices keeps lookup operations constant time. The logic is straightforward and makes a good baseline solution when solving array and grid-based interview problems.
Approach 2: Using the Matrix Itself (O(mn) time, O(1) space)
The optimal solution removes the need for extra storage by using the first row and first column of the matrix as markers. During the first pass, when a zero appears at matrix[i][j], mark the row and column by setting matrix[i][0] and matrix[0][j] to zero. Because the first row and column are reused as markers, track whether they originally contained zeros using two boolean flags. In a second pass, iterate through the inner matrix and zero out cells based on the markers stored in the first row and column. Finally update the first row and column if their flags were set.
The key insight is that the matrix already provides enough space to store row/column markers. This reduces the auxiliary memory from O(m+n) to O(1). The algorithm still performs two linear scans of the grid, so the runtime remains O(mn). Problems like this frequently appear in interviews to test whether you can reuse existing memory instead of allocating extra structures such as a hash table.
Recommended for interviews: Interviewers usually expect the in-place marker approach. Starting with the extra-space solution shows clear thinking and correctness. Improving it to reuse the first row and column demonstrates stronger optimization skills and awareness of space complexity constraints.
Approach 1: Approach 1: Using Additional Space
This approach uses two additional arrays to track the rows and columns that need to be zeroed.
- Traverse the matrix and mark rows and columns that need to be zeroed.
- Then, update the matrix based on the values in these arrays.
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
row = [False] * m
col = [False] * n
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row[i] = True
col[j] = True
for i in range(m):
for j in range(n):
if row[i] or col[j]:
matrix[i][j] = 0import java.util.*;
public class MatrixZero {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
col[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
}#include <vector>
using namespace std;
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<bool> row(m, false);
vector<bool> col(n, false);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == 0) {
row[i] = true;
col[j] = true;
}
}
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}function setZeroes(matrix) {
let m = matrix.length;
let n = matrix[0].length;
let row = new Array(m).fill(false);
let col = new Array(n).fill(false);
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
row[i] = true;
col[j] = true;
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}#include <stdio.h>
#include <stdbool.h>
void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
bool row[matrixSize];
bool col[*matrixColSize];
for(int i = 0; i < matrixSize; ++i) row[i] = false;
for(int i = 0; i < *matrixColSize; ++i) col[i] = false;
for (int i = 0; i < matrixSize; ++i) {
for (int j = 0; j < *matrixColSize; ++j) {
if (matrix[i][j] == 0) {
row[i] = true;
col[j] = true;
}
}
}
for (int i = 0; i < matrixSize; ++i) {
for (int j = 0; j < *matrixColSize; ++j) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}public class Solution {
public void SetZeroes(int[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
bool[] row = new bool[m];
bool[] col = new bool[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
col[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
}Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(m + n) for the boolean lists.
Approach 2: Approach 2: Using the Matrix Itself
This approach uses the matrix itself to track zeroes.
- Use the first row and column as markers.
- Traverse the matrix and if an element is zero, mark its row and column.
- Traverse again and set matrix elements to zero based on marked rows and columns.
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
col0 = 1
for i in range(m):
if matrix[i][0] == 0:
col0 = 0
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
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
if matrix[0][0] == 0:
for j in range(n):
matrix[0][j] = 0
if col0 == 0:
for i in range(m):
matrix[i][0] = 0public class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean isCol = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) isCol = true;
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 (matrix[0][0] == 0) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (isCol) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}#include <vector>
using namespace std;
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int col0 = 1;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) col0 = 0;
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 (matrix[0][0] == 0) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (col0 == 0) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}function setZeroes(matrix) {
let m = matrix.length;
let n = matrix[0].length;
let col0 = 1;
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) col0 = 0;
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
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;
}
}
}
if (matrix[0][0] === 0) {
for (let j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (col0 === 0) {
for (let i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}#include <stdio.h>
#include <stdbool.h>
void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
int isCol = 1;
int R = matrixSize;
int C = *matrixColSize;
for (int i = 0; i < R; i++) {
if (matrix[i][0] == 0) isCol = 0;
for (int j = 1; j < C; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (matrix[0][0] == 0) {
for (int j = 0; j < C; j++) {
matrix[0][j] = 0;
}
}
if (isCol == 0) {
for (int i = 0; i < R; i++) {
matrix[i][0] = 0;
}
}
}public class Solution {
public void SetZeroes(int[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
bool isCol = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) isCol = true;
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 (matrix[0][0] == 0) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (isCol) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1).
Approach 3: Array Mark
We use arrays rows and cols to mark the rows and columns to be cleared.
Then traverse the matrix again, and clear the elements in the rows and columns marked in rows and cols.
The time complexity is O(mtimes n), and the space complexity is O(m+n). Where m and n are the number of rows and columns of the matrix respectively.
/**
Do not return anything, modify matrix in-place instead.
*/
function setZeroes(matrix: number[][]): void {
const m = matrix.length;
const n = matrix[0].length;
const row: boolean[] = Array(m).fill(false);
const col: boolean[] = Array(n).fill(false);
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (matrix[i][j] === 0) {
row[i] = col[j] = true;
}
}
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}func setZeroes(matrix [][]int) {
row := make([]bool, len(matrix))
col := make([]bool, len(matrix[0]))
for i := range matrix {
for j, x := range matrix[i] {
if x == 0 {
row[i] = true
col[j] = true
}
}
}
for i := range matrix {
for j := range matrix[i] {
if row[i] || col[j] {
matrix[i][j] = 0
}
}
}
}impl Solution {
pub fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
let m = matrix.len();
let n = matrix[0].len();
let mut row = vec![false; m];
let mut col = vec![false; n];
for i in 0..m {
for j in 0..n {
if matrix[i][j] == 0 {
row[i] = true;
col[j] = true;
}
}
}
for i in 0..m {
for j in 0..n {
if row[i] || col[j] {
matrix[i][j] = 0;
}
}
}
}
}Approach 4: Mark in Place
In the first method, we use an additional array to mark the rows and columns to be cleared. In fact, we can also use the first row and first column of the matrix to mark them, without creating an additional array.
Since the first row and the first column are used to mark, their values may change due to the mark, so we need additional variables i0, j0 to mark whether the first row and the first column need to be cleared.
The time complexity is O(mtimes n), and the space complexity is O(1). Where m and n are the number of rows and columns of the matrix respectively.
/**
Do not return anything, modify matrix in-place instead.
*/
function setZeroes(matrix: number[][]): void {
const m = matrix.length;
const n = matrix[0].length;
const i0 = matrix[0].includes(0);
const j0 = matrix.map(row => row[0]).includes(0);
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;
}
}
}
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;
}
}
}
if (i0) {
matrix[0].fill(0);
}
if (j0) {
for (let i = 0; i < m; ++i) {
matrix[i][0] = 0;
}
}
}func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
i0, j0 := false, false
for j := 0; j < n; j++ {
if matrix[0][j] == 0 {
i0 = true
break
}
}
for i := 0; i < m; i++ {
if matrix[i][0] == 0 {
j0 = true
break
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][j] == 0 {
matrix[i][0], matrix[0][j] = 0, 0
}
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
if i0 {
for j := 0; j < n; j++ {
matrix[0][j] = 0
}
}
if j0 {
for i := 0; i < m; i++ {
matrix[i][0] = 0
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Additional Space | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Space Complexity: O(m + n) for the boolean lists. |
| Approach 2: Using the Matrix Itself | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Space Complexity: O(1). |
| Array Mark | – |
| Mark in Place | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Additional Space (Row & Column Sets) | O(mn) | O(m+n) | Best for clarity and quick implementation when memory usage is not restricted |
| Using Matrix as Markers (First Row & Column) | O(mn) | O(1) | Preferred interview solution when minimizing extra space is required |
Frequently asked questions
Is Set Matrix Zeroes easy or hard?
Set Matrix Zeroes is classified as a medium difficulty problem. The base idea of marking rows and columns is straightforward, but the in-place optimization that achieves O(1) space requires careful handling of the first row and column.
How to solve Set Matrix Zeroes in O(1) space?
Reuse the matrix itself to store row and column markers. Use the first row and first column to mark which rows or columns should become zero. After marking, iterate through the inner matrix and update cells based on those markers, then finally update the first row and column if needed. This keeps space complexity constant while maintaining O(mn) time.
What is the best approach for Set Matrix Zeroes?
The optimal approach uses the first row and first column of the matrix as markers. When a zero is found at position (i, j), mark matrix[i][0] and matrix[0][j] as zero to indicate the entire row and column should be cleared later. Two flags track whether the first row or column originally contained zeros. This solution runs in O(mn) time with O(1) extra space.
What data structure is used in Set Matrix Zeroes?
The straightforward solution uses sets or boolean arrays to track which rows and columns should be zeroed. The optimized solution avoids extra data structures by storing markers directly inside the matrix's first row and first column.
What is the time complexity of Set Matrix Zeroes?
Both common solutions run in O(mn) time where m is the number of rows and n is the number of columns. The algorithm scans the matrix once to detect zeros and another pass to apply updates. The difference between approaches is the space complexity.
Set Matrix Zeroes Python or Java solution availability
Solutions are typically implemented with nested loops that scan the matrix and update values based on markers. Implementations in Python, Java, C++, C, C#, and JavaScript follow the same algorithmic structure with O(mn) runtime.
Is Set Matrix Zeroes asked at Google or Amazon interviews?
Set Matrix Zeroes is a common medium-level matrix problem that has appeared in interviews at companies like Amazon, Google, and Meta. It tests grid traversal, careful state tracking, and the ability to optimize space usage in an in-place algorithm.