Set Matrix Zeroes

Q: What is the time complexity of Set Matrix Zeroes?

O(m·n) for an m × n matrix, since every cell is read and written a constant number of times. No solution does better, because any skipped cell could be the 0 that changes the answer. Extra space is O(m + n) with marker arrays and O(1) with the first row and column as markers.

MediumArrays and strings Hashing

+10

The input is an m × n grid of integers, given row by row, so matrix[i][j] sits in row i and column j. Wherever the grid holds a 0, set that whole row and that whole column to 0. Only the zeros present at the start count: a cell you turn into 0 does not clear its own row or column. You may change the grid in place; return it.

Function

setZeroes(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: the grid of integers, one inner list per row
Returnsinteger-2d-array: the matrix with every row and every column that held a 0 set to 0

Constraints

m == matrix.length and n == matrix[i].length
1 ≤ m, n ≤ 1000 and m × n ≤ 5000
All m rows hold n values.
-1000 ≤ matrix[i][j] ≤ 1000

Examples

Input: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
Output: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
Explanation: The only 0 sits in row 1, column 1. Row 1 becomes all zeros, and so does column 1, which turns the 8 and the 6 into 0. The four corners are in neither line and keep their values.

Follow-up

The best approach below keeps two extra booleans. Can you make do with one, letting matrix[0][0] stand for the first row?

Solution

A 0 you write looks exactly like a 0 you were given, so clearing lines during the scan spreads zeros across the matrix. Separate reading from writing: first record which rows and columns held a 0, then clear them. Keep that record in two arrays, or, for O(1) extra space, in the matrix's own first row and column.

Mark rows and columns in two arrays

Intuition

A cell ends up 0 exactly when its row or its column held a 0 at the start. So record two lists of facts, zeroRow[i] and zeroCol[j], in a pass that never writes, then clear every cell whose row or column is marked. Nothing spreads, because all reading is done before the first write.

Each pass visits the m·n cells once, so the time is O(m·n), and the arrays hold m + n booleans.

Algorithm

Create zeroRow with m entries and zeroCol with n entries, all false.
Scan every cell. When matrix[i][j] is 0, set zeroRow[i] and zeroCol[j] to true.
Scan every cell again and set it to 0 when zeroRow[i] or zeroCol[j] is true.
Return the matrix.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    zero_row = [False] * m
    zero_col = [False] * n
    # Pass 1: only read, so a new zero can never spread further.
    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.
    for i in range(m):
        for j in range(n):
            if zero_row[i] or zero_col[j]:
                matrix[i][j] = 0
    return matrix

Use the first row and column as the markers

Intuition

The first column has one cell per row and the first row one per column, the shapes of the two marker arrays. So a 0 at row i, column j writes 0 into matrix[i][0] and matrix[0][j]. That loses nothing: each of those cells lies in a line that must become 0 anyway.

Row 0 and column 0 are data as well as markers, and a marker there hides whether they held a 0 of their own. So check them first and keep the answers in two booleans. Mark and fill only cells with i ≥ 1 and j ≥ 1, and clear row 0 and column 0 last, because the fill reads them.

In the second example the 3 at row 1, column 1 survives because its markers, matrix[1][0] = 9 and matrix[0][1] = 4, are not 0. Time stays O(m·n) with two booleans of extra memory (O(m·n) in R, which copies the input first).

Algorithm

Set firstRowZero if row 0 holds a 0 and firstColZero if column 0 holds a 0.
For every cell with i ≥ 1 and j ≥ 1 that holds 0, set matrix[i][0] and matrix[0][j] to 0.
For every cell with i ≥ 1 and j ≥ 1, set it to 0 when matrix[i][0] or matrix[0][j] is 0.
If firstRowZero, set row 0 to 0. If firstColZero, set column 0 to 0.
Return the matrix.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    # The first row and column will hold the markers, so remember first
    # whether they need to become zero themselves.
    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: a zero inside the matrix flags its row in column 0
    # and its column in row 0.
    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 inside from the markers.
    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
    # The marker row and column go last.
    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
    return matrix

Pitfalls and edge cases

Clearing a row and a column as soon as you find a 0. In the first example the new 0 at row 1, column 2 then clears column 2, and only the 3 in the top left survives.
Letting matrix[0][0] mark both row 0 and column 0. In [[1, 2, 3], [0, 5, 6], [7, 8, 9]] the 0 in column 0 then wrongly clears row 0.
Clearing row 0 or column 0 before the fill. In [[0, 2, 3], [4, 5, 6], [7, 8, 9]] every column then looks marked, and the whole matrix becomes 0.
Forgetting single lines. With one row, the loops that start at 1 do nothing and the booleans do all the work: [[1, 0, 3]] must become [[0, 0, 0]].

Frequently asked questions3

Why can't you set the zeros while you scan the matrix?

A 0 you write looks the same as an original 0. When the scan reaches it, it clears its own row and column, and those new zeros spread further. Record every original zero before you change any cell.

What is the time complexity of Set Matrix Zeroes?

O(m·n) for an m × n matrix, since every cell is read and written a constant number of times. No solution does better, because any skipped cell could be the 0 that changes the answer. Extra space is O(m + n) with marker arrays and O(1) with the first row and column as markers.

Can you mark cells with a special value instead of 0?

Some solutions write a placeholder into the cells to clear and turn placeholders into zeros at the end. That works only if the placeholder can never appear in the input, which an integer matrix rarely guarantees. Writing it along a row and a column for each 0 also costs O(m·n·(m + n)) time.

def setZeroes(matrix):
    # Write code here

Test #1

Test #2

Argument

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

Expected Output

[[3, 0, 1], [0, 0, 0], [2, 0, 4]]