Game of Life

Medium· in-place· state encoding

Problem

A board of cells is either alive (1) or dead (0). Each cell's next state depends on its eight neighbours: a live cell survives with 2 or 3 live neighbours, and a dead cell becomes alive with exactly 3. Compute the next generation in place, with every cell updated simultaneously.

Examples

Input: board = [[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]]

Input: board = [[1,1],[1,0]]

Output: [[1,1],[1,1]]

Constraints

• 1 <= m, n <= 25
• board[i][j] is 0 or 1

Hints & approach

Hint 1

Updating cells one at a time corrupts the neighbour counts of later cells.

Hint 2

Each cell only uses one bit — store the next state in a spare bit.

Hint 3

Keep the current state in bit 0 and write the next state into bit 1, then shift everything right at the end.

Approachtry the hints first

Encode two generations in each cell. When counting neighbours, read only bit 0 (cell & 1), which still holds the current state. If the cell should be alive next generation, set bit 1 (cell |= 2). After processing every cell, shift each value right by one so bit 1 becomes the new state. This avoids copying the board.

Time O(m·n) · Space O(1)

← PreviousSearch a 2D Matrix DoneBack to Matrix / 2D