Matrices

Set Matrix Zeroes

medium

DESCRIPTION (inspired by Leetcode.com)

Write a function to modify an m x n integer matrix matrix directly, such that if any element in the matrix is 0, its entire corresponding row and column are set to 0. This transformation should be done in place, without using any additional data structures for storage.

Input:

matrix = [
    [0,2,3],
    [4,5,6],
    [7,8,9]
]

Output:

[
    [0,0,0],
    [0,5,6],
    [0,8,9]
]

Explanation: Since the element at the first row and first column is 0, set all elements in the first row and first column to 0.

Code Editor

Run your code to see results here

Have suggestions or found something wrong?

Understanding the Problem

The naive approach would use O(m + n) extra space by storing which rows and columns need to be zeroed in separate sets. But we can do better by using the matrix itself as storage.

Use the Matrix Itself!

Instead of extra arrays, we can use the first row and first column as markers. When we find a zero at [i][j], we mark:

matrix[i][0] = 0 → "row i needs to be zeroed"
matrix[0][j] = 0 → "column j needs to be zeroed"

But there's a catch! If we modify the first row/column while scanning, we'll lose information about whether they originally had zeros. So we save that first.

Walkthrough

Let's trace through matrix = [[1,1,1],[1,0,1],[1,1,1]]:

Step 1: Save first row/column state

Check if the first row or column originally contains any zeros. Save in boolean flags.

Step 2: Mark zeros using first row/column

Scan the inner matrix [1:][1:]. When we find a zero, mark the corresponding first row and first column cells.

Step 3: Zero the inner matrix

Use the markers to zero out cells. If matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0.

Step 4: Handle first row/column

If our saved flags indicate the first row/column originally had zeros, zero them now.

The order is crucial: we must save the first row/column state before using them as markers, and zero them last so we don't corrupt the markers we're reading.

Solution

Try these examples:

Visualization


def setZeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
    first_col_zero = any(matrix[i][0] == 0 for i in range(rows))
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    if first_row_zero:
        for j in range(cols):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(rows):
            matrix[i][0] = 0

Set Matrix Zeroes - O(1) space solution

0 / 15

What is the time complexity of this solution?

O(m × n)

O(x * y)

O(m * n * 4^L)

O(V + E)

Mark as read