The Game of Life, also known simply as Life, is a cellular automaton introduced by British mathematician John Horton Conway in 1970.

We are given an $m \times n$ grid representing the board. Each cell has one of two states:

• 1 → Alive cell

• 0 → Dead cell

Each cell interacts with its eight neighbors (horizontal, vertical, and diagonal) according to the following rules:

1. An alive cell with fewer than 2 alive neighbors dies → underpopulation.

2. An alive cell with 2 or 3 alive neighbors survives → lives to the next generation.

3. An alive cell with more than 3 alive neighbors dies → overpopulation.

4. A dead cell with exactly 3 alive neighbors becomes an alive cell → reproduction.

The board is updated using the above rules, with all updates applied simultaneously across the board. This means the next state of the grid is determined from the current state without interference from ongoing updates.

Given the current state of the board, your task is to update the board to reflect its next state.

Note: You do not need to return anything.

Constraints:

• $m ==$ board.length

• $n==$ board[i].length

• $1 \leq m, n \leq 25$

• board[i][j] is either 0 or 1.

The core intuition is to update all cells simultaneously without corrupting neighbor counts. We encode transitions in place: 1 means alive (and may stay alive), -1 means was alive and will die (underpopulation/overpopulation), 0 means dead (and may stay dead), and 2 means was dead and will become alive (reproduction). While counting neighbors, we only care about the original state, so we test abs(board[r][c]) == 1. This is true for 1 and -1 (originally alive) and false for 0 and 2 (originally dead). With that, we finish a full pass marking transitions, then a quick second pass to normalize to 0 or 1.

Using the intuition above, we implement the algorithm as follows:

1. Store the board’s dimensions in rows and cols.

2. Define an array neighbors = {-1, 0, 1}. The Cartesian product {−1,0,1} × {−1,0,1} gives the relative offsets to all eight neighboring cells around a given cell. We skip the (0, 0) pair as it represents the cell itself. This allows us to systematically check every neighbor’s state when counting alive cells.

3. Iterate over every cell (row, col) in the grid. For each cell:

   1. Initialize a counter liveNeighbors = 0.

   2. To count alive neighbors, loop i = 0..2 and j = 0..2 to form a relative offset (neighbors[i], neighbors[j]):

      1. Compute the neighbor’s coordinates: r = row + neighbors[i] and c = col + neighbors[j].

      2. If (r, c) is in bounds and abs(board[r][c]) == 1 (originally alive), increment liveNeighbors.

   3. After counting liveNeighbors, apply the Game of Life rules using the cell’s original state (the current value before any normalization):

      1. If board[row][col] == 1 and liveNeighbors is less than 2 (underpopulation) or greater than 3 (overpopulation), mark it as -1 to encode alive → dead.

      2. Otherwise, if board[row][col] == 0 and liveNeighbors is 3, mark it as 2 to encode dead → alive (reproduction).

      3. Otherwise, leave the cell unchanged (1 stays 1, 0 stays 0).

4. Iterate through the board again to finalize the next generation by normalizing each cell back to 0 or 1:

   1. If board[row][col] > 0 (values 1 or 2), set it to 1.

   2. Otherwise (for values 0 or -1), set it to 0.

5. The normalized board now represents the next state after applying the rules simultaneously.

Let’s look at the following illustration to get a better understanding of the solution: