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
- Separate reading from writing. A first pass only looks. A second pass only changes.
- Remember one bit per line. Instead of checking rows and columns again for every cell, keep a set
rowsof row numbers that contain an original 0, and a setcolsfor columns. - Pass one: for each cell equal to 0, add its row to
rowsand its column tocols. Nothing is changed yet, so no new zero can be mistaken for an old one. - Pass two: set a cell to 0 if its row is in
rowsor its column is incols. - 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] = 0In 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O(R · C · (R + C)): every cell scans its row and column | O(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 average | O(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.
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.
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?
Reading and writing must be separated, or new zeros are mistaken for original ones. The immediate-zero approach spreads zeros too far, and rescanning the changing grid has the same problem.
2. What is the time and space of the shown code on an R × C grid?
Two passes cost O(R · C), and the sets hold at most R row numbers and C column numbers. The first option is the brute force, and the last uses more space than the sets.
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?
The scan reaches the zero in row 1 and only then learns that row 1 and column 1 are bad. Cells before it stay unchanged. Running the variant gives this partly fixed grid.
Score 60% or more and the lesson is marked complete.