Advance Game of Life with Reduced Auxiliary Storage
Company: Additive Ai
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement `game_of_life(board)` to advance a rectangular binary grid by one generation. A value of `1` is alive and `0` is dead. A cell's neighbors are the horizontally, vertically, and diagonally adjacent cells within the grid; the edges do not wrap.
Determine every next state from the original generation:
- A live cell survives with exactly two or three live neighbors and otherwise dies.
- A dead cell becomes alive with exactly three live neighbors and otherwise stays dead.
Update `board` in place and return the resulting grid so the function's result can be compared across languages. The return value is an interface adaptation of the original in-place exercise. Reduce auxiliary storage while preserving simultaneous-update semantics; previously updated states must not affect the current generation's neighbor counts.
The board has 1 through 25 rows and 1 through 25 columns. Every row has the same length and every input entry is `0` or `1`.
### Examples
```text
game_of_life([[0,1,0],[0,0,1],[1,1,1],[0,0,0]])
-> [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
game_of_life([[1,1],[1,0]])
-> [[1,1],[1,1]]
```
Problem reference: [LeetCode 289](https://leetcode.com/problems/game-of-life/).
Overview: Advance Game of Life by one generation while preserving simultaneous updates, handling grid boundaries, and reducing storage in an in-place implementation.
Implement `game_of_life(board)` to advance a rectangular binary grid by one generation. A value of `1` is alive and `0` is dead. A cell's neighbors are the horizontally, vertically, and diagonally adjacent cells within the grid; the edges do not wrap.
Determine every next state from the original generation:
- A live cell survives with exactly two or three live neighbors and otherwise dies.
- A dead cell becomes alive with exactly three live neighbors and otherwise stays dead.
Update `board` in place and return the resulting grid so the function's result can be compared across languages. The return value is an interface adaptation of the original in-place exercise. Reduce auxiliary storage while preserving simultaneous-update semantics; previously updated states must not affect the current generation's neighbor counts.
The board has 1 through 25 rows and 1 through 25 columns. Every row has the same length and every input entry is `0` or `1`.
### Examples
```text
game_of_life([[0,1,0],[0,0,1],[1,1,1],[0,0,0]])
-> [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
game_of_life([[1,1],[1,0]])
-> [[1,1],[1,1]]
```
Problem reference: [LeetCode 289](https://leetcode.com/problems/game-of-life/).
Constraints
- board has 1 through 25 rows and 1 through 25 columns.
- Every row has equal length and every input value is 0 or 1.
- Neighbors are the eight adjacent in-bounds cells; edges do not wrap.
- Use the original generation for every transition, mutate board in place, and return the resulting grid.
Examples
Input: ([[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]],)
Expected Output: [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]
Explanation: The first public example evolves all cells simultaneously.
Input: ([[1, 1], [1, 0]],)
Expected Output: [[1, 1], [1, 1]]
Explanation: The three live cells survive and the fourth cell is born, as in the second example.
Hints
- Only cells within the grid are neighbors.
- A current live cell and a current dead cell obey different survival and birth conditions.