Set Matrix Zeroes (LC 73): O(1) Space In-Place Markers

Set Matrix Zeroes (LeetCode 73): if a cell is 0, zero its entire row and column in place. Record zero rows and columns in O(m + n) space, or reuse the first row and column as markers for O(1) extra space in O(m*n) time.

Language Selection

Choose your preferred programming language

Showing: Python

Set Matrix Zeroes

Problem Statement

You are given an m x n integer matrix. For every cell that contains 0 in the original matrix, change every value in that cell’s row and in that cell’s column to 0. Modify the matrix in place; the function returns nothing.

Only zeros that were present at the start count. A cell that becomes 0 because of this process does not wipe out its own row and column.

Examples

Example 1:

Input: matrix = [[4,2,7],[1,0,5],[3,8,6]]
Output: [[4,0,7],[0,0,0],[3,0,6]]
Explanation: The only zero is at row 1, column 1, so row 1 and column 1 are cleared.

Example 2:

Input: matrix = [[0,3,5,2],[6,9,1,0],[7,4,8,3]]
Output: [[0,0,0,0],[0,0,0,0],[0,4,8,0]]
Explanation: Zeros at (0,0) and (1,3) clear rows 0 and 1 and columns 0 and 3.

Example 3:

Input: matrix = [[-5,9]]
Output: [[-5,9]]
Explanation: There is no zero, so nothing changes.

Constraints

  • m == matrix.length, n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1

Approach 1: Record Zero Rows and Columns

Algorithm

Zeroing cells while we scan is the classic trap: newly written zeros would look like original zeros and spread to rows and columns that should stay intact. So we separate the work into two passes. The first pass only reads and records which rows and columns contain a zero. The second pass writes.

  1. Create boolean arrays zeroRow of size m and zeroCol of size n.
  2. Scan every cell. If matrix[i][j] == 0, set zeroRow[i] = true and zeroCol[j] = true.
  3. Scan every cell again. If zeroRow[i] or zeroCol[j] is true, set matrix[i][j] = 0.

Implementation

Python:

from typing import List


class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        zero_row = [False] * m
        zero_col = [False] * n

        # Pass 1: only read, remember which rows/columns hold a zero
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    zero_row[i] = True
                    zero_col[j] = True

        # Pass 2: write zeros
        for i in range(m):
            for j in range(n):
                if zero_row[i] or zero_col[j]:
                    matrix[i][j] = 0

Java:

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] zeroRow = new boolean[m];
        boolean[] zeroCol = new boolean[n];

        // Pass 1: only read, remember which rows/columns hold a zero
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    zeroRow[i] = true;
                    zeroCol[j] = true;
                }
            }
        }

        // Pass 2: write zeros
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (zeroRow[i] || zeroCol[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

Go:

func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])
    zeroRow := make([]bool, m)
    zeroCol := make([]bool, n)

    // Pass 1: only read, remember which rows/columns hold a zero
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == 0 {
                zeroRow[i] = true
                zeroCol[j] = true
            }
        }
    }

    // Pass 2: write zeros
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if zeroRow[i] || zeroCol[j] {
                matrix[i][j] = 0
            }
        }
    }
}

JavaScript:

function setZeroes(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const zeroRow = new Array(m).fill(false);
    const zeroCol = new Array(n).fill(false);

    // Pass 1: only read, remember which rows/columns hold a zero
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === 0) {
                zeroRow[i] = true;
                zeroCol[j] = true;
            }
        }
    }

    // Pass 2: write zeros
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (zeroRow[i] || zeroCol[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

C#:

public class Solution {
    public void SetZeroes(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        bool[] zeroRow = new bool[m];
        bool[] zeroCol = new bool[n];

        // Pass 1: only read, remember which rows/columns hold a zero
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    zeroRow[i] = true;
                    zeroCol[j] = true;
                }
            }
        }

        // Pass 2: write zeros
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (zeroRow[i] || zeroCol[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<bool> zeroRow(m, false), zeroCol(n, false);

        // Pass 1: only read, remember which rows/columns hold a zero
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    zeroRow[i] = true;
                    zeroCol[j] = true;
                }
            }
        }

        // Pass 2: write zeros
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (zeroRow[i] || zeroCol[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

Complexity Analysis

  • Time: O(m * n): two full scans of the matrix.
  • Space: O(m + n) for the two marker arrays.

Approach 2: First Row and Column as Markers (Optimal)

Algorithm

The marker arrays from Approach 1 can live inside the matrix itself. Use matrix[i][0] as the flag for row i and matrix[0][j] as the flag for column j. If a cell is zero, its row and column are going to be cleared anyway, so overwriting the matching first-row and first-column cells with 0 loses no information we still need.

The one complication: the first row and first column are flags and data at the same time. Before using them as flags, record in two booleans whether they originally contained a zero, and clear them last.

  1. Set firstRowZero = whether row 0 contains a zero, and firstColZero = whether column 0 contains a zero.
  2. For every cell with i >= 1 and j >= 1: if matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
  3. For every cell with i >= 1 and j >= 1: if matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0.
  4. If firstRowZero, zero all of row 0. If firstColZero, zero all of column 0.

Steps 2 and 3 never touch row 0 or column 0 as data cells, so the flags stay intact until step 4. Because values can be any 32-bit integer, there is no safe “sentinel” value to mark cells; reusing 0 itself avoids that problem.

Implementation

Python:

from typing import List


class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        # Remember the first row/column before they become flag storage
        first_row_zero = any(matrix[0][j] == 0 for j in range(n))
        first_col_zero = any(matrix[i][0] == 0 for i in range(m))

        # Mark: matrix[i][0] flags row i, matrix[0][j] flags column j
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        # Fill the inner cells from the flags
        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

        # Finally clear the first row/column themselves if needed
        if first_row_zero:
            for j in range(n):
                matrix[0][j] = 0
        if first_col_zero:
            for i in range(m):
                matrix[i][0] = 0

Java:

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        // Remember the first row/column before they become flag storage
        boolean firstRowZero = false, firstColZero = false;
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) firstRowZero = true;
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) firstColZero = true;
        }

        // Mark: matrix[i][0] flags row i, matrix[0][j] flags column j
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Fill the inner cells from the flags
        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;
                }
            }
        }

        // Finally clear the first row/column themselves if needed
        if (firstRowZero) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }
        if (firstColZero) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
}

Go:

func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])
    // Remember the first row/column before they become flag storage
    firstRowZero, firstColZero := false, false
    for j := 0; j < n; j++ {
        if matrix[0][j] == 0 {
            firstRowZero = true
        }
    }
    for i := 0; i < m; i++ {
        if matrix[i][0] == 0 {
            firstColZero = true
        }
    }

    // Mark: matrix[i][0] flags row i, matrix[0][j] flags column j
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }

    // Fill the inner cells from the flags
    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
            }
        }
    }

    // Finally clear the first row/column themselves if needed
    if firstRowZero {
        for j := 0; j < n; j++ {
            matrix[0][j] = 0
        }
    }
    if firstColZero {
        for i := 0; i < m; i++ {
            matrix[i][0] = 0
        }
    }
}

JavaScript:

function setZeroes(matrix) {
    const m = matrix.length, n = matrix[0].length;
    // Remember the first row/column before they become flag storage
    const firstRowZero = matrix[0].some(v => v === 0);
    const firstColZero = matrix.some(row => row[0] === 0);

    // Mark: matrix[i][0] flags row i, matrix[0][j] flags column j
    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;
            }
        }
    }

    // Fill the inner cells from the flags
    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;
            }
        }
    }

    // Finally clear the first row/column themselves if needed
    if (firstRowZero) {
        matrix[0].fill(0);
    }
    if (firstColZero) {
        for (let i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

C#:

public class Solution {
    public void SetZeroes(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        // Remember the first row/column before they become flag storage
        bool firstRowZero = false, firstColZero = false;
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) firstRowZero = true;
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) firstColZero = true;
        }

        // Mark: matrix[i][0] flags row i, matrix[0][j] flags column j
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Fill the inner cells from the flags
        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;
                }
            }
        }

        // Finally clear the first row/column themselves if needed
        if (firstRowZero) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }
        if (firstColZero) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        // Remember the first row/column before they become flag storage
        bool firstRowZero = false, firstColZero = false;
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) firstRowZero = true;
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) firstColZero = true;
        }

        // Mark: matrix[i][0] flags row i, matrix[0][j] flags column j
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Fill the inner cells from the flags
        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;
                }
            }
        }

        // Finally clear the first row/column themselves if needed
        if (firstRowZero) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }
        if (firstColZero) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
    }
};

Complexity Analysis

  • Time: O(m * n): a constant number of passes over the matrix.
  • Space: O(1) extra: two booleans; the flags are stored in the matrix itself.

Key Insights

  1. Read before you write. Any approach that zeros cells during the first scan confuses new zeros with original ones. Every correct solution separates “find” from “fill”.
  2. Only rows and columns matter. You do not need the positions of the zeros, just which rows and which columns contain one: m + n bits of information.
  3. The matrix can store its own flags. Cells in a row that will be cleared are free to overwrite, so the first row and column can hold the flags.
  4. The corner cell is shared. matrix[0][0] belongs to both row 0 and column 0, which is why the first row and first column each need their own boolean.

Edge Cases

  1. Single cell: [[0]] stays [[0]]; [[7]] stays [[7]].
  2. Single row: [[1,0,3]] becomes [[0,0,0]].
  3. Single column: [[1],[0],[3]] becomes [[0],[0],[0]].
  4. Zero in the corner: [[0,1],[1,1]] becomes [[0,0],[0,1]]; only row 0 and column 0 are cleared.
  5. Extreme values: cells equal to -2^31 or 2^31 - 1 must survive untouched when their row and column have no zero.

Common Mistakes

  1. Zeroing in the first pass. The new zeros cascade and eventually wipe out far more than they should.
  2. Using a sentinel such as -1 or Integer.MIN_VALUE to mark cells. Any 32-bit value can appear in the input, so the sentinel can collide with real data.
  3. Using matrix[0][0] for both the first row and the first column. You need a separate flag for one of them (or both, as here); otherwise a zero in the first column wrongly clears row 0 or vice versa.
  4. Clearing the first row or column too early. If row 0 held a zero and you clear it before step 3, every column flag reads as zero and the whole matrix is wiped.
  5. Returning a new matrix. The task is in place; on LeetCode a returned copy is ignored.

Interview Tips

  1. Explain why the naive in-place scan fails with a tiny example before writing code; it shows you see the trap.
  2. Present the O(m + n) solution first. It is clean and correct, and then the O(1) version reads as an optimisation of it.
  3. Call out the corner cell explicitly when you move to O(1) space. It is the detail interviewers check for.
  4. Write the order of the four steps on the whiteboard before coding: record first row/column, mark, fill, clear first row/column.

Follow-up Questions

  1. Count the cells that are zero afterwards without modifying the matrix: zr * n + zc * m - zr * zc, where zr and zc are the numbers of zero rows and zero columns.
  2. Sparse or huge matrices: if zeros are rare, store only their coordinates; if the matrix is streamed row by row, keep the column flags and buffer rows.
  3. Game of Life (LC 289): another in-place update where you must not read already-updated values; encode old and new states together.
  4. Rotate Image (LC 48): another in-place matrix transformation with no extra grid.
  5. Diagonals: how would you also clear both diagonals through each zero? The same marker idea works with m + n - 1 flags per diagonal direction.