73. Set Matrix Zeroes (Medium)

Problem

Given an m × n integer matrix, if a cell is 0, set its entire row and column to 0. Do it in place; try for $O(1)$ extra space as a follow-up.

Example

• matrix = [[1,1,1],[1,0,1],[1,1,1]] → [[1,0,1],[0,0,0],[1,0,1]]
• matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] → [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

LeetCode 73 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, make a copy

Snapshot the matrix; identify zero rows and columns from the snapshot; then write zeroes back into the original.

Python

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    snapshot = [row[:] for row in matrix]
    zero_rows = {r for r in range(rows)
                 if any(snapshot[r][c] == 0 for c in range(cols))}
    zero_cols = {c for c in range(cols)
                 if any(snapshot[r][c] == 0 for r in range(rows))}
    for r in range(rows):
        for c in range(cols):
            if r in zero_rows or c in zero_cols:
                matrix[r][c] = 0

Swift

final class Solution {
    func setZeroes(_ matrix: inout [[Int]]) {
        guard !matrix.isEmpty, !matrix[0].isEmpty else { return }
        let snapshot = matrix
        for row in snapshot.indices {
            for column in snapshot[row].indices where snapshot[row][column] == 0 {
                for targetRow in matrix.indices { matrix[targetRow][column] = 0 }
                for targetColumn in matrix[row].indices { matrix[row][targetColumn] = 0 }
            }
        }
    }
}

The snapshot is what makes it correct: without it, the in-place writes would propagate (“a zero I just wrote would trigger more zero-outs”). With a snapshot, the writes only depend on the original state.

Complexity

• Time: $O(m · n)$.
• Space: $O(m · n)$.

Doesn’t meet the in-place requirement.

Approach 2: Two boolean arrays ($O(m + n)$ space)

Collect which rows and columns contain a 0; then zero them.

Python

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])    # L1: O(1)
    zero_rows = [False] * rows                  # L2: O(m)
    zero_cols = [False] * cols                  # L3: O(n)

    for r in range(rows):                       # L4: first pass, m·n iterations
        for c in range(cols):
            if matrix[r][c] == 0:
                zero_rows[r] = True             # L5: O(1)
                zero_cols[c] = True             # L6: O(1)

    for r in range(rows):                       # L7: second pass, m·n iterations
        for c in range(cols):
            if zero_rows[r] or zero_cols[c]:
                matrix[r][c] = 0               # L8: O(1)

TypeScript

function setZeroes(matrix: number[][]): void {
    const rows = matrix.length, cols = matrix[0].length;    // L1: O(1)
    const zeroRows = new Array(rows).fill(false);           // L2: O(m)
    const zeroCols = new Array(cols).fill(false);           // L3: O(n)

    for (let r = 0; r < rows; r++) {                       // L4: first pass, m*n iterations
        for (let c = 0; c < cols; c++) {
            if (matrix[r][c] === 0) {
                zeroRows[r] = true;                        // L5: O(1)
                zeroCols[c] = true;                        // L6: O(1)
            }
        }
    }

    for (let r = 0; r < rows; r++) {                       // L7: second pass, m*n iterations
        for (let c = 0; c < cols; c++) {
            if (zeroRows[r] || zeroCols[c]) {
                matrix[r][c] = 0;                          // L8: O(1)
            }
        }
    }
}

Go

func setZeroes(matrix [][]int) {
    rows, cols := len(matrix), len(matrix[0])    // L1: O(1)
    zeroRows := make([]bool, rows)               // L2: O(m)
    zeroCols := make([]bool, cols)               // L3: O(n)

    for r := 0; r < rows; r++ {                 // L4: first pass, m*n iterations
        for c := 0; c < cols; c++ {
            if matrix[r][c] == 0 {
                zeroRows[r] = true               // L5: O(1)
                zeroCols[c] = true               // L6: O(1)
            }
        }
    }

    for r := 0; r < rows; r++ {                 // L7: second pass, m*n iterations
        for c := 0; c < cols; c++ {
            if zeroRows[r] || zeroCols[c] {
                matrix[r][c] = 0                 // L8: O(1)
            }
        }
    }
}

Swift

final class Solution {
    func setZeroes(_ matrix: inout [[Int]]) {
        guard !matrix.isEmpty, !matrix[0].isEmpty else { return }
        var zeroRows = Array(repeating: false, count: matrix.count)
        var zeroColumns = Array(repeating: false, count: matrix[0].count)
        for row in matrix.indices {
            for column in matrix[row].indices where matrix[row][column] == 0 {
                zeroRows[row] = true
                zeroColumns[column] = true
            }
        }
        for row in matrix.indices {
            for column in matrix[row].indices where zeroRows[row] || zeroColumns[column] {
                matrix[row][column] = 0
            }
        }
    }
}

Where the time goes, line by line

Variables: m = number of rows, n = number of columns.

Line	Per-call cost	Times executed	Contribution
L2-L3 (init flag arrays)	$O(1)$	m + n	$O(m + n)$
L4-L6 (first scan)	$O(1)$	m·n	$O(m·n)$ ← dominates
L7-L8 (second scan)	$O(1)$	m·n	$O(m·n)$

Two full passes over the matrix, each $O(m·n)$.

Complexity

• Time: $O(m · n)$, driven by L4/L5/L6 and L7/L8 (two full matrix scans).
• Space: $O(m + n)$ for the flag arrays.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: First row and column as markers ($O(1)$ space, canonical)

Use the first row and column themselves as flag arrays. Track separately whether the first row / first column themselves need zeroing.

Python

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][c] == 0 for c in range(cols))    # L1: O(n)
    first_col_zero = any(matrix[r][0] == 0 for r in range(rows))    # L2: O(m)

    # Use first row/col as markers
    for r in range(1, rows):                    # L3: mark pass (m-1)·(n-1)
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = 0               # L4: O(1)
                matrix[0][c] = 0               # L5: O(1)

    # Zero based on markers
    for r in range(1, rows):                    # L6: apply pass (m-1)·(n-1)
        for c in range(1, cols):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0               # L7: O(1)

    if first_row_zero:
        for c in range(cols):
            matrix[0][c] = 0                   # L8: O(n)
    if first_col_zero:
        for r in range(rows):
            matrix[r][0] = 0                   # L9: O(m)

TypeScript

function setZeroes(matrix: number[][]): void {
    const rows = matrix.length, cols = matrix[0].length;
    const firstRowZero = matrix[0].some(v => v === 0);             // L1: O(n)
    const firstColZero = matrix.some(row => row[0] === 0);         // L2: O(m)

    // Use first row/col as markers
    for (let r = 1; r < rows; r++) {                               // L3: mark pass
        for (let c = 1; c < cols; c++) {
            if (matrix[r][c] === 0) {
                matrix[r][0] = 0;                                  // L4: O(1)
                matrix[0][c] = 0;                                  // L5: O(1)
            }
        }
    }

    // Zero based on markers
    for (let r = 1; r < rows; r++) {                               // L6: apply pass
        for (let c = 1; c < cols; c++) {
            if (matrix[r][0] === 0 || matrix[0][c] === 0) {
                matrix[r][c] = 0;                                  // L7: O(1)
            }
        }
    }

    if (firstRowZero) for (let c = 0; c < cols; c++) matrix[0][c] = 0;  // L8: O(n)
    if (firstColZero) for (let r = 0; r < rows; r++) matrix[r][0] = 0;  // L9: O(m)
}

Go

func setZeroes(matrix [][]int) {
    rows, cols := len(matrix), len(matrix[0])
    firstRowZero := false
    for c := 0; c < cols; c++ { if matrix[0][c] == 0 { firstRowZero = true; break } }  // L1: O(n)
    firstColZero := false
    for r := 0; r < rows; r++ { if matrix[r][0] == 0 { firstColZero = true; break } }  // L2: O(m)

    // Use first row/col as markers
    for r := 1; r < rows; r++ {                    // L3: mark pass
        for c := 1; c < cols; c++ {
            if matrix[r][c] == 0 {
                matrix[r][0] = 0                   // L4: O(1)
                matrix[0][c] = 0                   // L5: O(1)
            }
        }
    }

    // Zero based on markers
    for r := 1; r < rows; r++ {                    // L6: apply pass
        for c := 1; c < cols; c++ {
            if matrix[r][0] == 0 || matrix[0][c] == 0 {
                matrix[r][c] = 0                   // L7: O(1)
            }
        }
    }

    if firstRowZero { for c := 0; c < cols; c++ { matrix[0][c] = 0 } }  // L8: O(n)
    if firstColZero { for r := 0; r < rows; r++ { matrix[r][0] = 0 } }  // L9: O(m)
}

Swift

final class Solution {
    func setZeroes(_ matrix: inout [[Int]]) {
        guard !matrix.isEmpty, !matrix[0].isEmpty else { return }
        let firstRowHasZero = matrix[0].contains(0)
        let firstColumnHasZero = matrix.contains { $0[0] == 0 }
        if matrix.count > 1 && matrix[0].count > 1 {
            for row in 1..<matrix.count {
                for column in 1..<matrix[row].count where matrix[row][column] == 0 {
                    matrix[row][0] = 0
                    matrix[0][column] = 0
                }
            }
            for row in 1..<matrix.count {
                for column in 1..<matrix[row].count where matrix[row][0] == 0 || matrix[0][column] == 0 {
                    matrix[row][column] = 0
                }
            }
        }
        if firstRowHasZero { matrix[0] = Array(repeating: 0, count: matrix[0].count) }
        if firstColumnHasZero {
            for row in matrix.indices { matrix[row][0] = 0 }
        }
    }
}

Where the time goes, line by line

Variables: m = number of rows, n = number of columns.

Line	Per-call cost	Times executed	Contribution
L1-L2 (first row/col check)	$O(1)$	m + n	$O(m + n)$
L3-L5 (mark pass)	$O(1)$	(m-1)·(n-1)	$O(m·n)$ ← dominates
L6-L7 (apply pass)	$O(1)$	(m-1)·(n-1)	$O(m·n)$
L8-L9 (fix first row/col)	$O(1)$	m + n	$O(m + n)$

Three linear passes total; two of them are $O(m·n)$, two are $O(m + n)$.

Complexity

• Time: $O(m · n)$, driven by L3/L4/L5 and L6/L7 (two full inner-matrix scans).
• Space: $O(1)$ extra.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Copy + overwrite	$O(m · n)$	$O(m · n)$
Boolean flag arrays	$O(m · n)$	$O(m + n)$
First row/col as markers	$O(m · n)$	$O(1)$

“Reuse the input as auxiliary storage” is a recurring in-place trick.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_073.py and run.
# Uses the canonical implementation (Approach 3: first row/col as markers).
# set_zeroes() modifies the matrix in place.

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][c] == 0 for c in range(cols))
    first_col_zero = any(matrix[r][0] == 0 for r in range(rows))

    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0

    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0

    if first_row_zero:
        for c in range(cols):
            matrix[0][c] = 0
    if first_col_zero:
        for r in range(rows):
            matrix[r][0] = 0

def _run_tests():
    m = [[1,1,1],[1,0,1],[1,1,1]]
    set_zeroes(m)
    assert m == [[1,0,1],[0,0,0],[1,0,1]]

    m2 = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
    set_zeroes(m2)
    assert m2 == [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

    m3 = [[1]]  # no zeroes
    set_zeroes(m3)
    assert m3 == [[1]]

    m4 = [[0]]  # single zero
    set_zeroes(m4)
    assert m4 == [[0]]

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function setZeroes(matrix: number[][]): void {
    const rows = matrix.length, cols = matrix[0].length;
    const firstRowZero = matrix[0].some(v => v === 0);
    const firstColZero = matrix.some(row => row[0] === 0);
    for (let r = 1; r < rows; r++)
        for (let c = 1; c < cols; c++)
            if (matrix[r][c] === 0) { matrix[r][0] = 0; matrix[0][c] = 0; }
    for (let r = 1; r < rows; r++)
        for (let c = 1; c < cols; c++)
            if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;
    if (firstRowZero) for (let c = 0; c < cols; c++) matrix[0][c] = 0;
    if (firstColZero) for (let r = 0; r < rows; r++) matrix[r][0] = 0;
}

const m = [[1,1,1],[1,0,1],[1,1,1]];
setZeroes(m);
console.assert(JSON.stringify(m) === JSON.stringify([[1,0,1],[0,0,0],[1,0,1]]));
const m2 = [[0,1,2,0],[3,4,5,2],[1,3,1,5]];
setZeroes(m2);
console.assert(JSON.stringify(m2) === JSON.stringify([[0,0,0,0],[0,4,5,0],[0,3,1,0]]));
const m3 = [[1]]; setZeroes(m3);
console.assert(JSON.stringify(m3) === JSON.stringify([[1]]));
const m4 = [[0]]; setZeroes(m4);
console.assert(JSON.stringify(m4) === JSON.stringify([[0]]));
console.log('all tests pass');

Related data structures

• Arrays, in-place marking strategy

Related concepts

• Array Scans, the linear pass habit of carrying just enough state while reading each item once.
• Simulation, the explicit state model for executing rules exactly while keeping cases organized.