LeetEye LeetEye
Medium Math & Geometry ~5 min

Set Matrix Zeroes

math-and-geometry set-matrix-zeroes

Problem

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

Examples

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]]
Key Insight

Use first row and column as markers. Scan for zeros, mark in first row/col, then fill zeros.

Use first row to mark columns, first column to mark rows. Handle row 0 separately. Fill inner cells, then first row/col.

How to Approach This Problem

Pattern Recognition: When you see keywords like set matrix zeroes math-and-geometry, think Math & Geometry.

Step-by-Step Reasoning

1 Why can't we zero cells immediately when we find a 0?
Answer: We'd lose information about original zeros
New zeros would trigger more zeroing incorrectly. Need to mark first, then zero.
2 We can use O(1) extra space by:
Answer: Using first row/column as markers
First row marks columns to zero. First column marks rows to zero.
3 matrix[0][0] belongs to both first row and column. Handle by:
Answer: Either A or B
Need to separately track whether row 0 or col 0 should be zeroed.
4 After marking, we should fill zeros:
Answer: From (1,1) to (m-1, n-1), then first row/col
Fill inner matrix first. If we zero first row/col early, we lose marker info.
5 If matrix[0][j] = 0 after scanning:
Answer: Column j should be zeroed
First row marks which columns to zero (either original 0 or 0 found below).

Solution

def setZeroes(matrix: List[List[int]]) -> None:
    m, n = len(matrix), len(matrix[0])
    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 zeros in first row/col
    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 zeros for inner matrix
    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
    
    # Handle first row/col
    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

Complexity Analysis

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

Master This Pattern

Build intuition with interactive MCQs. Practice Math & Geometry problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye