Next Generation of the Colony
MediumMatrix
Problem
A petri dish is modelled as an m × n grid where 1 is a living cell and 0 an empty one. Each cell has up to eight neighbours (horizontal, vertical and diagonal); cells outside the dish do not exist. All cells update simultaneously to the next generation:
a living cell with two or three living neighbours survives, otherwise it dies; an empty cell with exactly three living neighbours becomes alive, otherwise it stays empty.
Update grid in place to the next generation using O(1) extra memory. The function returns nothing.
Example 1
- Input:
- grid = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]
- Output:
- [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]
For example, (1, 0) is empty with exactly three living neighbours (0,1), (2,0), (2,1), so it is born.
Example 2
- Input:
- grid = [[0, 0, 0], [1, 1, 1], [0, 0, 0]]
- Output:
- [[0, 1, 0], [0, 1, 0], [0, 1, 0]]
A horizontal bar of three flips to a vertical one.
Constraints
- 1 ≤ m, n ≤ 200
- grid[i][j] is 0 or 1
Hint
Show the first hint
If you overwrite a cell with its next state immediately, its neighbours will count the wrong value. You need both the old and the new state for a while.
Walkthrough
How to approach it
01Clarify before coding
- Do neighbours wrap around the edges? No, cells outside the grid do not exist.
- Is the update simultaneous? Yes, every cell uses the previous generation's neighbours.
- Is a full copy allowed? It is the obvious version, but the target is O(1) extra memory.
02Brute force
Copy the grid, compute each cell's next state from the copy and write it into the original.
Cost: O(m · n · 8) time and O(m · n) extra memory for the copy.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.