FastPrepGame of Life: In-Place Next Generation

Game of Life: In-Place Next Generation

Google logoGoogle● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

Given a finite rectangular binary grid board, compute one simultaneous generation of Conway's Game of Life.

  • A live cell with two or three live neighbors survives.
  • A dead cell with exactly three live neighbors becomes live.
  • Every other cell is dead in the next generation.

Each cell has up to eight horizontal, vertical, and diagonal neighbors. Cells outside the grid are dead. Every decision must use the original generation.

Modify the supplied board in place and return it. You may encode temporary old/new state in each cell, but you must not allocate another grid proportional to the board size.

Function

gameOfLife(board: int[][]) → int[][]

Examples

Example 1

board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]return = [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Neighbor counts come from the original four-row grid, so all births and deaths occur simultaneously.

Example 2

board = [[1,1],[1,0]]return = [[1,1],[1,1]]

The dead corner has three live neighbors and is born; each original live cell has two neighbors and survives.

Example 3

board = [[0,0,0],[1,1,1],[0,0,0]]return = [[0,1,0],[0,1,0],[0,1,0]]

The horizontal blinker becomes vertical when every cell reads the same original generation.

Constraints

  • 1 <= board.length, board[r].length <= 200.
  • Every row has equal length and every cell is 0 or 1.
  • The update must use O(1) auxiliary space beyond the returned board.

More Google problems

See Google hiring insights
public int[][] gameOfLife(int[][] board) {
    // write your code here
}
board[[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
expected[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
Checking account…