Set Matrix Zeroes

MediumMatrix · In-Place Markers🧩 Matrix Traversal LeetCode #73 ↗Updated Oct 30, 2026

Problem

For an m × n integer grid, whenever a cell holds 0 its whole row and whole column must become 0. Only zeros present in the original grid count. Modify the grid in-place.

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

Input[[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]]

1 ≤ m, n ≤ 200 · -2³¹ ≤ matrix[i][j] ≤ 2³¹-1 · Follow-up: O(1) extra space.

Try it yourself

Java

class Solution {
    public void setZeroes(int[][] matrix) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Separate recording from writing: you only need one flag per row and per column — and row 0 / column 0 of the grid itself can hold those flags, as long as you first remember whether they had their own zeros.

PatternMatrix Traversal

Instinct A 2D grid you must walk in a fixed geometric order (spiral, diagonal, layer, rotate) or update in place - think boundaries, direction vectors and index maths.

Memory hack Walk the walls, then shrink the room - four fences (top, bottom, left, right) close in after every lap.

Open the Matrix Traversal guide →

Approaches

Brute ForceCopy Grid, Zero Row & Column per Zero

Time O(m·n·(m+n))Space O(m·n)

Read zeros from the untouched original but write into a copy, so newly written zeros can't cascade. For every zero found, wipe its row and column in the copy (O(m+n) each), then copy back.

Java

public void setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    int[][] copy = new int[rows][];
    for (int r = 0; r < rows; r++) copy[r] = matrix[r].clone();
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == 0) {
                for (int k = 0; k < cols; k++) copy[r][k] = 0;
                for (int k = 0; k < rows; k++) copy[k][c] = 0;
            }
        }
    }
    for (int r = 0; r < rows; r++) System.arraycopy(copy[r], 0, matrix[r], 0, cols);
}

Correct, but a grid full of zeros costs O(mn(m+n)) time and O(mn) memory.

BetterRow & Column Flag Arrays

Time O(m·n)Space O(m+n)

A cell ends up zero iff its row or its column had a zero. Record that in zeroRows[] / zeroCols[] in one pass, then apply it in a second pass — each cell is visited twice.

Java

public void setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    boolean[] zeroRows = new boolean[rows];
    boolean[] zeroCols = new boolean[cols];
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == 0) {
                zeroRows[r] = true;
                zeroCols[c] = true;
            }
        }
    }
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (zeroRows[r] || zeroCols[c]) matrix[r][c] = 0;
        }
    }
}

Linear time; the only waste is the O(m+n) flag arrays.

OptimalFirst Row/Column as Markers

Time O(m·n)Space O(1)

Reuse matrix[r][0] and matrix[0][c] as the flag arrays. Because those cells are overwritten by flags, first save two booleans saying whether row 0 / column 0 originally had a zero. Zero the interior from the markers, and handle row 0 and column 0 last so the markers stay valid.

Java

public void setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;
    for (int c = 0; c < cols; c++) if (matrix[0][c] == 0) firstRowZero = true;
    for (int r = 0; r < rows; r++) if (matrix[r][0] == 0) firstColZero = true;
    for (int r = 1; r < rows; r++) {             // mark
        for (int c = 1; c < cols; c++) {
            if (matrix[r][c] == 0) {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }
    for (int r = 1; r < rows; r++) {             // apply to interior
        for (int c = 1; c < cols; c++) {
            if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
        }
    }
    if (firstRowZero) for (int c = 0; c < cols; c++) matrix[0][c] = 0;
    if (firstColZero) for (int r = 0; r < rows; r++) matrix[r][0] = 0;
}

Linear time, constant extra space — answers the follow-up.

Pro tip

Never use a sentinel like -1 or MIN_VALUE as a marker — any int can legally appear in the grid.

At a glance

Level	Approach	Time	Space
Brute Force	Copy Grid, Zero Row & Column per Zero	`O(m·n·(m+n))`	`O(m·n)`
Better	Row & Column Flag Arrays	`O(m·n)`	`O(m+n)`
Optimal	First Row/Column as Markers	`O(m·n)`	`O(1)`

Common pitfalls

Zeroing in place while scanning — new zeros cascade and wipe the whole grid.
Zeroing row 0 / column 0 before the interior — destroys the markers.
Sharing matrix[0][0] for both row 0 and column 0 without a separate flag.

Interview tips

Explain why the result must depend only on original zeros.
Walk through O(mn) → O(m+n) → O(1) space as a deliberate progression.
Call out the processing order explicitly; it is the whole trick.

Pattern

Use the input as scratch space → O(1)-space follow-ups where row/column state fits in the grid's own border.

My notes saved in this browser