231. Life Step
A petri dish is a grid board where 1 marks a live cell and 0 an empty spot. Each spot has up to eight neighbours: the spots that touch it horizontally, vertically or diagonally. The whole dish changes at once in one step, using these rules: a live cell with fewer than 2 or more than 3 live neighbours dies; a live cell with 2 or 3 live neighbours survives; an empty spot with exactly 3 live neighbours becomes live; every other spot stays as it is.
Update board in place so that it holds the next state. All spots must change simultaneously, so the new values must be computed from the old state only. The dish can be large, so building a fresh copy of the whole board for each cell is too slow, and you should not need any big extra grid at all.
Example 1
- Input:
- board = [[0,1,0],[0,1,0],[0,1,0]]
- Output:
- [[0,0,0],[1,1,1],[0,0,0]]
- Explanation:
A vertical bar of three live cells flips into a horizontal bar: the middle cell has 2 live neighbours and survives, the ends have 1 and die, and the left and right cells of the middle row each have 3 live neighbours and are born.
Example 2
- Input:
- board = [[1,1],[1,1]]
- Output:
- [[1,1],[1,1]]
- Explanation:
Every live cell has exactly 3 live neighbours, so the 2x2 block is stable.
Example 3
- Input:
- board = [[1,1,0],[1,0,0],[0,0,0]]
- Output:
- [[1,1,0],[1,1,0],[0,0,0]]
- Explanation:
The empty centre has 3 live neighbours and becomes live; the three original cells each have 2 live neighbours and survive.
Constraints
1 ≤ board.length, board[0].length ≤ 500
board[i][j] is 0 or 1
Modify board in place; nothing is returned.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Graded
- Your answer is read from
boardafter your method returns. - Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(m × n)
- Space
- O(1)