# Game of Life
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/game-of-life)
Canonical: https://scaleengineer.com/dsa/problems/game-of-life
**Data structures:** Array, Matrix
**Companies:** [Dropbox](https://scaleengineer.com/companies/dropbox), [Google](https://scaleengineer.com/companies/google), [Snap](https://scaleengineer.com/companies/snap), [BitGo](https://scaleengineer.com/companies/bitgo), [Warnermedia](https://scaleengineer.com/companies/warnermedia), [Cloudflare](https://scaleengineer.com/companies/cloudflare), [Anduril](https://scaleengineer.com/companies/anduril), [Two Sigma](https://scaleengineer.com/companies/two-sigma)
---
## Problem
According to [Wikipedia's article](https://en.wikipedia.org/wiki/Conway%27s%5FGame%5Fof%5FLife): "The **Game of Life**, also known simply as **Life**, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

The board is made up of an `m x n` grid of cells, where each cell has an initial state: **live** (represented by a `1`) or **dead** (represented by a `0`). Each cell interacts with its [eight neighbors](https://en.wikipedia.org/wiki/Moore%5Fneighborhood) (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population.
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state of the board is determined by applying the above rules simultaneously to every cell in the current state of the `m x n` grid `board`. In this process, births and deaths occur **simultaneously**.

Given the current state of the `board`, **update** the `board` to reflect its next state.

**Note** that you do not need to return anything.

**Example 1:**

![](https://assets.glich.co/dsa/game-of-life/image0.jpg) 

**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]]

**Example 2:**

![](https://assets.glich.co/dsa/game-of-life/image1.jpg) 

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

**Constraints:**

* `m == board.length`
* `n == board[i].length`
* `1 <= m, n <= 25`
* `board[i][j]` is `0` or `1`.

**Follow up:**

* Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
* In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array (i.e., live cells reach the border). How would you address these problems?

# Approaches
## Using Additional Space
The most straightforward approach is to create a new grid to store the next state while processing the current grid.
**Time:** O(m*n), where m and n are the dimensions of the board · **Space:** O(m*n) to store the next state grid
**Pros:** Simple to understand and implement; No risk of mixing old and new states; Easy to debug
**Cons:** Uses extra space proportional to the board size; Requires additional copy operation at the end; Not memory efficient for large boards
### Explanation
In this approach, we create a new m x n grid to store the next state of the board. For each cell in the current board, we:

1. Count the number of live neighbors using the 8 adjacent cells
2. Apply the Game of Life rules to determine the next state
3. Store the result in the new grid
4. Finally, copy the new grid back to the original board

Here's the implementation:

```java
public void gameOfLife(int[][] board) {
    int m = board.length;
    int n = board[0].length;
    int[][] nextState = new int[m][n];
    
    // Define the 8 directions for neighbors
    int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    // Process each cell
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int liveNeighbors = 0;
            
            // Count live neighbors
            for (int k = 0; k < 8; k++) {
                int newX = i + dx[k];
                int newY = j + dy[k];
                
                if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
                    liveNeighbors += board[newX][newY];
                }
            }
            
            // Apply rules
            if (board[i][j] == 1) {
                if (liveNeighbors < 2 || liveNeighbors > 3) {
                    nextState[i][j] = 0;
                } else {
                    nextState[i][j] = 1;
                }
            } else {
                if (liveNeighbors == 3) {
                    nextState[i][j] = 1;
                }
            }
        }
    }
    
    // Copy back to original board
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = nextState[i][j];
        }
    }
}
```
### Algorithm
1. Create a new m x n grid `nextState`
2. For each cell (i,j) in the board:
   - Count live neighbors in all 8 directions
   - Apply Game of Life rules to determine next state
   - Store result in nextState[i][j]
3. Copy nextState back to original board

## In-place Solution using State Encoding
We can solve this problem in-place by using additional states to encode both the current and next states in the same cell.
**Time:** O(m*n), where m and n are the dimensions of the board · **Space:** O(1), only uses constant extra space
**Pros:** Uses constant extra space; No need for additional grid; Meets the follow-up requirement of in-place solution
**Cons:** More complex to understand and implement; Harder to debug due to state encoding; Less readable code
### Explanation
Instead of using a separate grid, we can use additional states to represent both the current and next states:
- 0: Dead -> Dead
- 1: Live -> Live
- 2: Live -> Dead
- 3: Dead -> Live

This way, we can determine the original state by checking if the number is 1 or 2 (originally live) or 0 or 3 (originally dead).

```java
public void gameOfLife(int[][] board) {
    int m = board.length;
    int n = board[0].length;
    
    int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    // First pass: mark the cells with new states
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int liveNeighbors = 0;
            
            // Count live neighbors
            for (int k = 0; k < 8; k++) {
                int newX = i + dx[k];
                int newY = j + dy[k];
                
                if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
                    // Count cells that are originally live (1 or 2)
                    if (board[newX][newY] == 1 || board[newX][newY] == 2) {
                        liveNeighbors++;
                    }
                }
            }
            
            // Apply rules using new states
            if (board[i][j] == 1) {
                if (liveNeighbors < 2 || liveNeighbors > 3) {
                    board[i][j] = 2; // Live -> Dead
                }
            } else if (board[i][j] == 0 && liveNeighbors == 3) {
                board[i][j] = 3; // Dead -> Live
            }
        }
    }
    
    // Second pass: restore to final states
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] %= 2; // Convert states back to 0 or 1
        }
    }
}
```
### Algorithm
1. Define new states:
   - 2: Live -> Dead
   - 3: Dead -> Live
2. First pass: For each cell
   - Count live neighbors (cells with value 1 or 2)
   - Apply rules using new states
3. Second pass: Convert all cells back to 0 or 1 using modulo operation

# Solutions
### CSharp

```csharp
public class Solution { public void GameOfLife ( int [][] board ) { int m = board . Length ; int n = board [ 0 ]. Length ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int live = - board [ i ][ j ]; for ( int x = i - 1 ; x <= i + 1 ; ++ x ) { for ( int y = j - 1 ; y <= j + 1 ; ++ y ) { if ( x >= 0 && x < m && y >= 0 && y < n && board [ x ][ y ] > 0 ) { ++ live ; } } } if ( board [ i ][ j ] == 1 && ( live < 2 || live > 3 )) { board [ i ][ j ] = 2 ; } if ( board [ i ][ j ] == 0 && live == 3 ) { board [ i ][ j ] = - 1 ; } } } for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( board [ i ][ j ] == 2 ) { board [ i ][ j ] = 0 ; } if ( board [ i ][ j ] == - 1 ) { board [ i ][ j ] = 1 ; } } } } }
```

### Java

```java
class Solution { public void gameOfLife ( int [][] board ) { int m = board . length , n = board [ 0 ]. length ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int live = - board [ i ][ j ]; for ( int x = i - 1 ; x <= i + 1 ; ++ x ) { for ( int y = j - 1 ; y <= j + 1 ; ++ y ) { if ( x >= 0 && x < m && y >= 0 && y < n && board [ x ][ y ] > 0 ) { ++ live ; } } } if ( board [ i ][ j ] == 1 && ( live < 2 || live > 3 )) { board [ i ][ j ] = 2 ; } if ( board [ i ][ j ] == 0 && live == 3 ) { board [ i ][ j ] = - 1 ; } } } for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( board [ i ][ j ] == 2 ) { board [ i ][ j ] = 0 ; } else if ( board [ i ][ j ] == - 1 ) { board [ i ][ j ] = 1 ; } } } } }
```

### CPP

```cpp
class Solution { public: void gameOfLife ( vector < vector < int >>& board ) { int m = board . size (), n = board [ 0 ]. size (); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int live = - board [ i ][ j ]; for ( int x = i - 1 ; x <= i + 1 ; ++ x ) { for ( int y = j - 1 ; y <= j + 1 ; ++ y ) { if ( x >= 0 && x < m && y >= 0 && y < n && board [ x ][ y ] > 0 ) { ++ live ; } } } if ( board [ i ][ j ] == 1 && ( live < 2 || live > 3 )) { board [ i ][ j ] = 2 ; } if ( board [ i ][ j ] == 0 && live == 3 ) { board [ i ][ j ] = - 1 ; } } } for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( board [ i ][ j ] == 2 ) { board [ i ][ j ] = 0 ; } else if ( board [ i ][ j ] == - 1 ) { board [ i ][ j ] = 1 ; } } } } };
```

### Python

```python
class Solution : def gameOfLife ( self , board : List [ List [ int ]]) -> None : m , n = len ( board ), len ( board [ 0 ]) for i in range ( m ): for j in range ( n ): live = - board [ i ][ j ] for x in range ( i - 1 , i + 2 ): for y in range ( j - 1 , j + 2 ): if 0 <= x < m and 0 <= y < n and board [ x ][ y ] > 0 : live += 1 if board [ i ][ j ] and ( live < 2 or live > 3 ): board [ i ][ j ] = 2 if board [ i ][ j ] == 0 and live == 3 : board [ i ][ j ] = - 1 for i in range ( m ): for j in range ( n ): if board [ i ][ j ] == 2 : board [ i ][ j ] = 0 elif board [ i ][ j ] == - 1 : board [ i ][ j ] = 1
```