LeetCode · #73

Set Matrix Zeroes Solution

If an element is 0, set its entire row and column to 0. Do it in-place.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #73

🏗️

Pattern

Matrix — in-place markers

Example

Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Section Two · Approach 1

Extra Arrays — O(m+n) space

Use boolean arrays rows[m] and cols[n] to mark which rows/cols should be zeroed.

Better: Use the first row and first column of the matrix itself as the marker arrays. O(1) extra space (just two booleans for "should first row/col themselves be zeroed").

Java — O(m+n) space

 class Solution {
public void setZeroes(int[][] m) {
int R = m.length, C = m[0].length;
boolean[] rows = new boolean[R], cols = new boolean[C];
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if (m[i][j] == 0) { rows[i] = true; cols[j] = true; }
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if (rows[i] || cols[j]) m[i][j] = 0;
    }
}

Python — O(m+n) space

 class Solution:
def setZeroes(self, m: list[list[int]]) -> None:
        R, C = len(m), len(m[0])
        rows = set(i for i in range(R) for j in range(C) if m[i][j] == 0)
        cols = set(j for i in range(R) for j in range(C) if m[i][j] == 0)
for i in range(R):
for j in range(C):
if i in rows or j in cols: m[i][j] = 0

Section Three · Approach 2

First Row/Col as Markers — O(1) space

Use matrix[0][j] and matrix[i][0] as markers. Two extra booleans track whether the first row/col themselves should be zeroed.

💡 Mental model: Instead of carrying a notepad (extra arrays), write your notes in the margins of the matrix (first row/column). After processing the body based on notes, decide whether to erase the margins themselves.

Algorithm

Check if first row/col contain any zeros → firstRowZero, firstColZero.
Scan rest of matrix: if m[i][j]==0, set m[i][0]=0 and m[0][j]=0.
Use markers: for i from 1..R-1, j from 1..C-1: if m[i][0]==0 || m[0][j]==0, set m[i][j]=0.
If firstRowZero: zero out first row. If firstColZero: zero out first col.

Section Four · Trace

Visual Walkthrough

Set Matrix Zeroes — Markers

Section Five · Implementation

Code — Java & Python

Java — O(1) space

 class Solution {
public void setZeroes(int[][] m) {
int R = m.length, C = m[0].length;
boolean fc = false;
for (int i = 0; i < R; i++) {
if (m[i][0] == 0) fc = true;
for (int j = 1; j < C; j++)
if (m[i][j] == 0) { m[i][0] = 0; m[0][j] = 0; }
        }
for (int i = R - 1; i >= 0; i--) {
for (int j = C - 1; j >= 1; j--)
if (m[i][0] == 0 || m[0][j] == 0) m[i][j] = 0;
if (fc) m[i][0] = 0;
        }
    }
}

Python — O(1) space

 class Solution:
def setZeroes(self, m: list[list[int]]) -> None:
        R, C = len(m), len(m[0])
        fc = any(m[i][0] == 0 for i in range(R))
for i in range(R):
for j in range(1, C):
if m[i][j] == 0: m[i][0] = m[0][j] = 0 for i in range(R - 1, -1, -1):
for j in range(C - 1, 0, -1):
if m[i][0] == 0 or m[0][j] == 0: m[i][j] = 0 if fc: m[i][0] = 0

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Extra arrays	O(m·n)	O(m+n)
First row/col markers ← optimal	O(m·n)	O(1)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
No zeros	`[[1,2],[3,4]]`	No changes.
All zeros	`[[0,0],[0,0]]`	Stays all zeros.
First cell zero	`[[0,1],[1,1]]`	First row AND first col zeroed. Need both markers.
Single row	`[[1,0,3]]`	Entire row becomes [0,0,0].

⚠ Common Mistake: Processing the first row/column markers before using them. If you zero the first row/col too early, you lose the marker information. Process the body first (rows 1..R-1, cols 1..C-1), then handle the first row/col last. Process backwards (bottom-right to top-left) to avoid overwriting markers.

← Back to Math & Bit problems

LearningTree

LC 73 · Set Matrix Zeroes — Solution & Explanation | DSA Guide