# LeetCode 289: Game of Life

## Problem Restatement

We are given an `m x n` board.

Each cell is either:

| Value | Meaning |
|---|---|
| `0` | Dead cell |
| `1` | Live cell |

Each cell has up to eight neighbors:

```python
horizontal
vertical
diagonal
```

The next board state is computed using these rules:

| Current State | Live Neighbors | Next State |
|---|---:|---|
| Live | Fewer than `2` | Dead |
| Live | `2` or `3` | Live |
| Live | More than `3` | Dead |
| Dead | Exactly `3` | Live |

All cells must update simultaneously.

That means when deciding the next state of one cell, we must use the original state of its neighbors, not already-updated values.

The official statement asks us to update the board in-place. The follow-up emphasizes that simultaneous updates make direct mutation tricky. The listed constraints include `1 <= m, n <= 25` and `board[i][j]` is either `0` or `1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | 2D integer array `board` |
| Output | Nothing |
| Mutation | Modify `board` in-place |
| Dead cell | `0` |
| Live cell | `1` |
| Neighbor directions | 8 directions |

Function shape:

```python
class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        ...
```

## Examples

For:

```python
board = [
    [0, 1, 0],
    [0, 0, 1],
    [1, 1, 1],
    [0, 0, 0],
]
```

The next state is:

```python
[
    [0, 0, 0],
    [1, 0, 1],
    [0, 1, 1],
    [0, 1, 0],
]
```

For:

```python
board = [
    [1, 1],
    [1, 0],
]
```

The next state is:

```python
[
    [1, 1],
    [1, 1],
]
```

The dead cell in the bottom-right corner has exactly three live neighbors, so it becomes live.

## First Thought: Use a Copy

The easiest correct method is to copy the original board first.

Then we read from the copy and write into the original board.

```python
class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        rows = len(board)
        cols = len(board[0])

        original = [row[:] for row in board]

        directions = [
            (-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1),
        ]

        for r in range(rows):
            for c in range(cols):
                live = 0

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if 0 <= nr < rows and 0 <= nc < cols:
                        if original[nr][nc] == 1:
                            live += 1

                if original[r][c] == 1:
                    if live < 2 or live > 3:
                        board[r][c] = 0
                else:
                    if live == 3:
                        board[r][c] = 1
```

This is simple and correct.

## Problem With the Copy Solution

The copy solution uses extra space proportional to the whole board.

For an `m x n` board, that is:

```python
O(m * n)
```

The follow-up asks for an in-place solution.

The challenge is that if we directly change a cell from `1` to `0`, later cells may count it as dead, even though it was originally live.

We need to store both:

1. The old state.
2. The next state.

inside the same cell.

## Key Insight

Use temporary encoded states.

We need to distinguish four cases:

| Encoded Value | Old State | New State |
|---:|---:|---:|
| `0` | Dead | Dead |
| `1` | Live | Live |
| `2` | Live | Dead |
| `-1` | Dead | Live |

The important trick is neighbor counting.

When counting live neighbors, a cell should count as originally live if its old state was `1`.

That means both of these should count as live:

```python
1
2
```

because `2` means the cell was live but will die.

These should count as originally dead:

```python
0
-1
```

because `-1` means the cell was dead but will become live.

So a neighbor is originally live when:

```python
board[nr][nc] > 0
```

After marking every cell, we do a second pass to convert temporary states into final states.

## Algorithm

Use two passes.

First pass:

For each cell:

1. Count originally live neighbors.
2. If the current cell is live:
   - It dies if live neighbors are fewer than `2` or greater than `3`.
   - Mark it as `2`.
3. If the current cell is dead:
   - It becomes live if live neighbors equal `3`.
   - Mark it as `-1`.

Second pass:

Convert temporary states:

| Value | Final Value |
|---:|---:|
| `2` | `0` |
| `-1` | `1` |
| `0` | `0` |
| `1` | `1` |

## Correctness

During the first pass, every cell still exposes its original state through its sign.

A value greater than `0` means the cell was originally live. A value less than or equal to `0` means the cell was originally dead.

Therefore, even after some cells have been marked with temporary values, neighbor counting still uses the original board state.

For each cell, the algorithm counts exactly the number of originally live neighbors among the eight surrounding cells.

Then it applies the Game of Life rules:

- A live cell with fewer than two live neighbors is marked to die.
- A live cell with two or three live neighbors remains live.
- A live cell with more than three live neighbors is marked to die.
- A dead cell with exactly three live neighbors is marked to become live.

So after the first pass, every cell contains both enough information about its original state and its correct next state.

The second pass replaces each encoded value with its final state.

Therefore, after the second pass, the board equals the simultaneous next state required by the problem.

## Complexity

Let:

```python
R = number of rows
C = number of columns
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(R * C)` | Each cell checks at most 8 neighbors |
| Space | `O(1)` | The board is updated in-place |

The factor `8` is constant, so the time complexity is linear in the number of cells.

## Implementation

```python
class Solution:
    def gameOfLife(self, board: list[list[int]]) -> None:
        rows = len(board)
        cols = len(board[0])

        directions = [
            (-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1),
        ]

        for r in range(rows):
            for c in range(cols):
                live = 0

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if nr < 0 or nr >= rows:
                        continue

                    if nc < 0 or nc >= cols:
                        continue

                    if board[nr][nc] > 0:
                        live += 1

                if board[r][c] == 1:
                    if live < 2 or live > 3:
                        board[r][c] = 2

                elif board[r][c] == 0:
                    if live == 3:
                        board[r][c] = -1

        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 2:
                    board[r][c] = 0
                elif board[r][c] == -1:
                    board[r][c] = 1
```

## Code Explanation

We first get the board size:

```python
rows = len(board)
cols = len(board[0])
```

Then we list the eight neighbor directions:

```python
directions = [
    (-1, -1), (-1, 0), (-1, 1),
    (0, -1),           (0, 1),
    (1, -1),  (1, 0),  (1, 1),
]
```

For each cell, we count originally live neighbors:

```python
if board[nr][nc] > 0:
    live += 1
```

This counts both `1` and `2` as originally live.

If the current cell is live and should die:

```python
if board[r][c] == 1:
    if live < 2 or live > 3:
        board[r][c] = 2
```

we mark it as `2`.

If the current cell is dead and should become live:

```python
elif board[r][c] == 0:
    if live == 3:
        board[r][c] = -1
```

we mark it as `-1`.

The second pass turns temporary states into final states:

```python
if board[r][c] == 2:
    board[r][c] = 0
elif board[r][c] == -1:
    board[r][c] = 1
```

Cells already equal to `0` or `1` stay unchanged.

## Testing

```python
def test_game_of_life():
    s = Solution()

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

    s.gameOfLife(board)

    assert board == [
        [0, 0, 0],
        [1, 0, 1],
        [0, 1, 1],
        [0, 1, 0],
    ]

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

    s.gameOfLife(board)

    assert board == [
        [1, 1],
        [1, 1],
    ]

    board = [[1]]
    s.gameOfLife(board)
    assert board == [[0]]

    board = [[0]]
    s.gameOfLife(board)
    assert board == [[0]]

    print("all tests passed")

test_game_of_life()
```

Test meaning:

| Test | Why |
|---|---|
| Standard board | Checks all four rules together |
| `2 x 2` block with one dead cell | Checks reproduction |
| Single live cell | Dies from under-population |
| Single dead cell | Stays dead |