DSA problem
Game of Life
According to Wikipedia article, the Game of Life, devised by mathematician John Conway, is a cellular automaton. The board is an m x n grid of cells, where each cell has an initial state: live (represented by 1) or dead (represented by 0). Each cell interacts with its eight neighbors (horizontal, vertical, and diagonal) using four rules.
A live cell with fewer than two live neighbors dies as if caused by under-population. A live cell with two or three live neighbors lives on to the next generation. A live cell with more than three live neighbors dies as if by over-population. A dead cell with exactly three live neighbors becomes a live cell as if by reproduction. The next state of the board is created by applying these rules simultaneously to every cell in the current state, where births and deaths occur at the same instant.
The straightforward solution copies the whole board so that neighbor counts always read the original generation, costing O(m * n) extra space. The challenge asks you to update the board in-place, which means a cell's new value must not corrupt the neighbor count of cells processed later.
The intuition for the optimal in-place approach is to encode both the old and new states in a single integer using bits. The least significant bit holds the current state, and the second bit holds the next state. When counting neighbors you read cell & 1 to recover the original value, while writing the next state into bit 2 with a left shift. After the whole grid is processed, a final pass right-shifts every cell by one to reveal the next generation, all without any auxiliary matrix.
Examples
board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]][[0,0,0],[1,0,1],[0,1,1],[0,1,0]]board = [[1,1],[1,0]][[1,1],[1,1]]board = [[0,0],[0,0]][[0,0],[0,0]]Constraints
- m == board.length
- n == board[i].length
- 1 <= m, n <= 25
- board[i][j] is 0 or 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.