LeetCode 73 · Math & Geometry

Set Matrix Zeroes, explained with a picture

Broken lights knock out their whole row and column.

MediumMath & Geometry
▶ Watch it step by step

The problem

If a cell in the grid is 0, set its entire row and column to 0. Do it in place.

Input:  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

Picture it

Picture a light panel where one dead bulb (0) blows its whole row and column. If we switched bulbs off while still scanning, the new zeros would wrongly spread further. So first remember which rows and columns contain an original 0, then switch them all off in a second pass.

How to recognise it

  • A cell's new value depends on whether its row or column contains an original 0.
  • The change must be done in place, so new zeros you write could be confused with original ones.
  • You must separate "what the grid was" from "what you are changing".
  • Sizes are small (up to 200 × 200), so the question is about order of operations, not speed.
  • Information about each row and column needs only one bit.

Start with brute force

For every cell, look along its row and its column in the original grid for a zero, and write the result into a copy.

import copy

def zeroes_brute(m):
    R, C = len(m), len(m[0])
    out = copy.deepcopy(m)
    for r in range(R):
        for c in range(C):
            row_has = any(m[r][k] == 0 for k in range(C))
            col_has = any(m[k][c] == 0 for k in range(R))
            if row_has or col_has:
                out[r][c] = 0
    return out

Each of the R · C cells scans R + C others, so time is O(R · C · (R + C)); for 200 × 200 that is about 16 million steps, slow but not impossible. Space is O(R · C) for the copy, and it returns a new grid instead of changing the given one.

A tempting shortcut is to zero a whole row and column the moment a 0 is seen. That is wrong: the zeros it writes look like original zeros when the scan reaches them, so zeroes spread too far (see below).

From brute force to the idea

  1. Separate reading from writing. A first pass only looks. A second pass only changes.
  2. Remember one bit per line. Instead of checking rows and columns again for every cell, keep a set rows of row numbers that contain an original 0, and a set cols for columns.
  3. Pass one: for each cell equal to 0, add its row to rows and its column to cols. Nothing is changed yet, so no new zero can be mistaken for an old one.
  4. Pass two: set a cell to 0 if its row is in rows or its column is in cols.
  5. Update the grid itself. Nothing is returned; the given grid is changed.

This is the key idea: record first, change later, with two small sets in the middle.

The key idea

Record zero rows/columns first (or use the first row and column as markers), then apply. O(rows × cols).

Python solution

def set_zeroes(m):
    rows, cols = set(), set()
    for r in range(len(m)):
        for c in range(len(m[0])):
            if m[r][c] == 0:
                rows.add(r); cols.add(c)   # remember first, change later
    for r in range(len(m)):
        for c in range(len(m[0])):
            if r in rows or c in cols:
                m[r][c] = 0

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(R · C · (R + C)): every cell scans its row and columnO(R · C): the copy
Row and column sets (shown code)O(R · C): two passes over the grid, each set lookup is O(1) on averageO(R + C): at most one entry per row and column

Using the first row and first column as the markers brings the space down to O(1) (see the try box).

Edge cases

  • No zeros: both sets stay empty and the grid is unchanged ([[1, 2], [3, 4]]).
  • All zeros: stays all zeros.
  • One zero in the middle ([[1,1,1],[1,0,1],[1,1,1]]): gives [[1,0,1],[0,0,0],[1,0,1]], a plus shape.
  • One row or column ([[1, 0, 3]] or [[1], [0], [3]]): the whole line becomes 0.
  • Zeros in the first row or column ([[0,1,2,0],[3,4,5,2],[1,3,1,5]]): gives [[0,0,0,0],[0,4,5,0],[0,3,1,0]].
  • Return value: the function returns None; the grid is changed in place.

Common mistakes

  • Zeroing the row and column as soon as a 0 is found. For [[1,1,1],[1,0,1],[1,1,1]] this gives [[1,0,0],[0,0,0],[0,0,0]] instead of the plus shape.
  • Fixing only the rows and forgetting the columns, which gives [[1,1,1],[0,0,0],[1,1,1]].
  • Merging the two passes into one with the sets, which tests cells before all zeros are known (see the quiz).
  • In the O(1)-space version, forgetting to save whether the first row and column held a zero before using them as markers.
Your turn: O(1) extra space

Do the same job without the two sets, using only a few variables. For [[1,2,3],[4,0,6],[7,8,9]] the result is [[1,0,3],[0,0,0],[7,0,9]]. Describe your approach, then write it if you like.

Compare with our answer

Use the first row and first column of the grid as the marker storage. Two extra booleans remember whether the first row and column themselves held a zero, because their markers would overwrite that information.

def set_zeroes_o1(m):
    R, C = len(m), len(m[0])
    first_row = any(m[0][c] == 0 for c in range(C))
    first_col = any(m[r][0] == 0 for r in range(R))
    for r in range(1, R):
        for c in range(1, C):
            if m[r][c] == 0:
                m[r][0] = m[0][c] = 0          # mark row r and column c
    for r in range(1, R):
        for c in range(1, C):
            if m[r][0] == 0 or m[0][c] == 0:
                m[r][c] = 0
    if first_row:
        for c in range(C): m[0][c] = 0
    if first_col:
        for r in range(R): m[r][0] = 0

It gives the same grids as the shown code on all my random tests. Time O(R · C), space O(1).

A strong answer mentions: using the first row and column as marker storage, saving whether they held zeros first, and handling them last.

Check what stuck

1. A grid has a few zeros. Every cell in the same row or column as a zero must become 0, and you may not copy the grid. Which approach fits best?

2. What is the time and space of the shown code on an R × C grid?

3. A learner merges the passes: inside the first loop, after the if m[r][c] == 0 check, they add if r in rows or c in cols: m[r][c] = 0. What does the grid [[1,1,1],[1,0,1],[1,1,1]] become?

Score 60% or more and the lesson is marked complete.