On this page
Description
Some grid problems compute a new grid from the old one, where every new value depends on old values elsewhere. The easy fix is a second grid of the same size. This skill does it without one, by borrowing storage the grid already has. Set Matrix Zeroes uses the first row and column as notes. Game of Life uses a spare bit inside each cell. Both need care about when you read a cell and when you write it.
We'll go from simple to more technical:
- The pattern: borrow the first row and column as markers, in ordered passes.
- A second flavor: keep the current and the next state in the same cell.
- Where packing two states into one cell shows up.
- The ordering bugs, and when there's no spare room.
The approach
Set Matrix Zeroes: wherever a cell is 0, clear its whole row and column. You can't clear as you go, because a cleared cell looks like an original zero and would clear more. So first write down which rows and columns to clear, then clear them. The notes go in row 0 and column 0. A 0 in matrix[r][0] means "clear row r", and a 0 in matrix[0][c] means "clear column c". Row 0 and column 0 need notes of their own, so save two flags for them before you start.
Here it is on a 3 x 4 grid with zeros at row 0, column 2 and at row 2, column 1. Bold values changed in that pass.
| Pass | Row 0 | Row 1 | Row 2 |
|---|---|---|---|
| Start | 1 2 0 4 | 5 6 7 8 | 9 0 2 3 |
| 0: row 0 has a zero, column 0 doesn't | 1 2 0 4 | 5 6 7 8 | 9 0 2 3 |
| 1: note the zero at row 2, column 1 | 1 0 0 4 | 5 6 7 8 | 0 0 2 3 |
| 2: clear inner cells whose row or column is noted | 1 0 0 4 | 5 0 0 8 | 0 0 0 0 |
| 3: the saved flag clears row 0 | 0 0 0 0 | 5 0 0 8 | 0 0 0 0 |
The original zero in row 0 already acts as the note for column 2. The flag from pass 0 is what tells pass 3 to clear row 0 itself. Without it, you couldn't tell an original zero in row 0 from a note written there in pass 1.
The four passes in short:
Pass 0: remember whether row 0 / column 0 themselves originally contain a zero.
Pass 1: for every matrix[r][c] == 0 with r, c >= 1, set matrix[r][0] = 0 and matrix[0][c] = 0.
Pass 2: for every r, c >= 1, zero matrix[r][c] if matrix[r][0] == 0 or matrix[0][c] == 0.
Pass 3: apply the saved row-0 / column-0 flags from Pass 0 last.
A second flavor: two states in one cell
Game of Life computes each cell's next state from its neighbors' current states. If you overwrite a cell right away, the cells after it read its new value instead of the old one. There's no idle row to borrow here. But each cell holds only 0 or 1, so the second bit of every int is free. Keep the current state in bit 0 and write the next state into bit 1:
| Value | Now | Next |
|---|---|---|
| 0 | dead | dead |
| 1 | alive | dead |
| 2 | dead | alive |
| 3 | alive | alive |
Java
// bit 0 = original state (never touched mid-pass), bit 1 = next state
if (nextAlive) board[r][c] |= 2;
// ...only after every cell in the grid has been visited this way:
board[r][c] >>= 1; // shifts next-state down into bit 0, discarding the original
Python
# bit 0 = original state (never touched mid-pass), bit 1 = next state
if next_alive:
board[r][c] |= 2
# ...only after every cell in the grid has been visited this way:
board[r][c] >>= 1 # shifts next-state down into bit 0, discarding the original
To read a neighbor's current state, look at bit 0 only: (board[nr][nc] & 1) == 1. A neighbor you've already processed may now hold 3 (alive, staying alive). A plain == 1 check would count it as dead.
Where you'll see it
Simulations and image filters face the same problem: a cell's new value depends on old values around it. Keeping both states in one cell avoids a second copy of a large grid. When memory isn't tight, the second copy is simpler and perfectly fine.
Which tool for which job?
| You need | Use |
|---|---|
| Clear rows and columns, O(1) extra space | the first row and column as markers, plus two flags |
| The same, when memory doesn't matter | two boolean arrays (rows, cols) - simpler |
| Next state from neighbors' current states | bit 0 = now, bit 1 = next; shift at the end |
| A huge or infinite board that's mostly empty | a set of live cells |
| Fast whole-grid passes | loop rows outside, columns inside |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Not recording whether row 0 / column 0 had zeros first | the marker row wipes itself | save two flags before pass 1 |
| Zeroing row 0 / column 0 before the rest | every cell reads "clear me" | apply the inner cells first, the markers last |
Checking a neighbor with == 1 after re-encoding | updated neighbors stop counting | read the current state with & 1 |
| Marking with a value that can appear in the data (-1) | real values get cleared | use the marker rows or spare bits |
| Looping columns outside, rows inside | the same result, several times slower | row-major order |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why save whether row 0 and column 0 had a zero before pass 1 starts?
Show answer
Pass 1 writes notes into row 0 and column 0. After that, a zero there could be an original zero or a note. The final pass needs to know whether row 0 and column 0 themselves should be cleared, so that has to be read before any note is written.
2. A Game of Life solution writes the next state into bit 1, then checks board[nr][nc] == 1 to see if a neighbor is alive. What's wrong?
Show answer
A neighbor that was alive and stays alive now holds 3, not 1. The == 1 check counts it as dead, so later cells see too few live neighbors. Read only the current-state bit: (board[nr][nc] & 1) == 1.
3. What goes wrong if pass 2 of Set Matrix Zeroes starts before pass 1 has finished?
Show answer
Pass 2 clears cells using an incomplete set of notes. A row or column whose zero pass 1 hasn't reached yet isn't noted, so its cells stay as they are. Find every zero first, then clear.
Key takeaways
- In-place marking reuses space the grid already has: an idle row and column, or spare bits in each cell.
- Read every cell's original meaning before any pass starts overwriting it.
- Set Matrix Zeroes keeps its notes in row 0 and column 0, plus two flags for those two lines.
- Game of Life keeps the next state in bit 1, reads the current state with
& 1, and shifts at the end.