Game Of Life

                                            
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        vector<vector<int>> copyBoard = board;
        int m = board.size();
        int n = board[0].size();
        
        vector<pair<int, int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = 0;
                for (auto dir : directions) {
                    int x = i + dir.first;
                    int y = j + dir.second;
                    if (x >= 0 && x < m && y >= 0 && y < n && copyBoard[x][y] == 1) {
                        liveNeighbors++;
                    }
                }
                
                if (copyBoard[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[i][j] = 0;
                } else if (copyBoard[i][j] == 0 && liveNeighbors == 3) {
                    board[i][j] = 1;
                }
            }
        }
    }
};

                                            
class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[][] temp = new int[m][n];
        
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = 0;
                
                for (int[] dir : directions) {
                    int newRow = i + dir[0];
                    int newCol = j + dir[1];
                    
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && board[newRow][newCol] == 1) {
                        liveNeighbors++;
                    }
                }
                
                if (board[i][j] == 1) {
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        temp[i][j] = 0;
                    } else {
                        temp[i][j] = 1;
                    }
                } else {
                    if (liveNeighbors == 3) {
                        temp[i][j] = 1;
                    }
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = temp[i][j];
            }
        }
    }
}

                                            
class Solution(object):
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: None Do not return anything, modify board in-place 
        instead.
        """
        neighbors = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]
        
        rows = len(board)
        cols = len(board[0])
        
        for i in range(rows):
            for j in range(cols):
                live_neighbors = 0
                
                for neighbor in neighbors:
                    x = i + neighbor[0]
                    y = j + neighbor[1]
                    
                    if 0 <= x < rows and 0 <= y < cols and abs(board[x][y]) == 1:
                        live_neighbors += 1
                
                if board[i][j] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                    board[i][j] = -1
                if board[i][j] == 0 and live_neighbors == 3:
                    board[i][j] = 2
        
        for i in range(rows):
            for j in range(cols):
                if board[i][j] > 0:
                    board[i][j] = 1
                else:
                    board[i][j] = 0

                                            
void gameOfLife(int** board, int boardSize, int* boardColSize) {
    int m = boardSize;
    int n = *boardColSize;
    
    int dirs[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int liveNeighbors = 0;
            for (int k = 0; k < 8; k++) {
                int x = i + dirs[k][0];
                int y = j + dirs[k][1];
                if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] == 1 || board[x][y] == 2)) {
                    liveNeighbors++;
                }
            }
            
            if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[i][j] = 2;
            }
            if (board[i][j] == 0 && liveNeighbors == 3) {
                board[i][j] = 3;
            }
        }
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] %= 2;
        }
    }
}

                                            
public class Solution {
    public void GameOfLife(int[][] board) {
        int m = board.Length;
        int n = board[0].Length;

        int[][] copyBoard = new int[m][];
        for (int i = 0; i < m; i++) {
            copyBoard[i] = new int[n];
            Array.Copy(board[i], copyBoard[i], n);
        }

        int[] dirX = {0, 1, 0, -1, 1, 1, -1, -1};
        int[] dirY = {1, 0, -1, 0, 1, -1, 1, -1};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = 0;

                for (int k = 0; k < 8; k++) {
                    int newX = i + dirX[k];
                    int newY = j + dirY[k];

                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && copyBoard[newX][newY] == 1) {
                        liveNeighbors++;
                    }
                }

                if (copyBoard[i][j] == 1) {
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        board[i][j] = 0;
                    }
                } else {
                    if (liveNeighbors == 3) {
                        board[i][j] = 1;
                    }
                }
            }
        }
    }
}

                                            
/**
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place 
instead.
 */
var gameOfLife = function(board) {
    const rows = board.length;
    const cols = board[0].length;

    const directions = [
        [-1, -1], [-1, 0], [-1, 1],
        [0, -1], [0, 1],
        [1, -1], [1, 0], [1, 1]
    ];

    const isValid = (r, c) => {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    };

    const getLiveNeighbors = (r, c) => {
        let liveNeighbors = 0;
        
        for (const [dr, dc] of directions) {
            const newRow = r + dr;
            const newCol = c + dc;
            
            if (isValid(newRow, newCol) && (board[newRow][newCol] === 1 || board[newRow][newCol] === 2)) {
                liveNeighbors++;
            }
        }
        
        return liveNeighbors;
    };

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            const liveNeighbors = getLiveNeighbors(r, c);
            
            if (board[r][c] === 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[r][c] = 2; // Next state dead
            }
            
            if (board[r][c] === 0 && liveNeighbors === 3) {
                board[r][c] = 3; // Next state alive
            }
        }
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            board[r][c] %= 2;
        }
    }
};

                                            
/**
 Do not return anything, modify board in-place instead.
 */
function gameOfLife(board: number[][]): void {
    const directions = [
        [0, 1],
        [0, -1],
        [1, 0],
        [-1, 0],
        [1, 1],
        [1, -1],
        [-1, 1],
        [-1, -1]
    ];

    const rows = board.length;
    const cols = board[0].length;

    const copyBoard = JSON.parse(JSON.stringify(board));

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            let liveNeighbors = 0;

            for (const [dx, dy] of directions) {
                const x = i + dx;
                const y = j + dy;

                if (x >= 0 && x < rows && y >= 0 && y < cols && copyBoard[x][y] === 1) {
                    liveNeighbors++;
                }
            }

            if (copyBoard[i][j] === 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[i][j] = 0;
            }

            if (copyBoard[i][j] === 0 && liveNeighbors === 3) {
                board[i][j] = 1;
            }
        }
    }
};

                                            
class Solution {
    /**
     * @param Integer[][] $board
     * @return NULL
     */
    function gameOfLife(&$board) {
        $directions = [
            [-1, -1], [-1, 0], [-1, 1],
            [0, -1],           [0, 1],
            [1, -1],  [1, 0],  [1, 1]
        ];
        
        $m = count($board);
        $n = count($board[0]);
        
        $copy = $board;
        
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                $liveNeighbors = 0;
                
                foreach ($directions as $dir) {
                    $ni = $i + $dir[0];
                    $nj = $j + $dir[1];
                    
                    if ($ni >= 0 && $ni < $m && $nj >= 0 && $nj < $n && $copy[$ni][$nj] == 1) {
                        $liveNeighbors++;
                    }
                }
                
                if ($copy[$i][$j] == 1) {
                    if ($liveNeighbors < 2 || $liveNeighbors > 3) {
                        $board[$i][$j] = 0;
                    }
                } else {
                    if ($liveNeighbors == 3) {
                        $board[$i][$j] = 1;
                    }
                }
            }
        }
    }
}

                                            
class Solution {
    func gameOfLife(_ board: inout [[Int]]) {
        let m = board.count
        let n = board[0].count
        
        let directions = [(1,0), (-1,0), (0,1), (0,-1), (1,1), (-1,-1), (1,-1), (-1,1)]
        
        for i in 0..<m {
            for j in 0..<n {
                var liveNeighbors = 0
                
                for dir in directions {
                    let x = i + dir.0
                    let y = j + dir.1
                    
                    if x >= 0 && x < m && y >= 0 && y < n && (board[x][y] == 1 || board[x][y] == 2) {
                        liveNeighbors += 1
                    }
                }
                
                if board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3) {
                    board[i][j] = 2
                }
                
                if board[i][j] == 0 && liveNeighbors == 3 {
                    board[i][j] = 3
                }
            }
        }
        
        for i in 0..<m {
            for j in 0..<n {
                if board[i][j] == 2 {
                    board[i][j] = 0
                } else if board[i][j] == 3 {
                    board[i][j] = 1
                }
            }
        }
    }
}

                                            
class Solution {
    fun gameOfLife(board: Array<IntArray>): Unit {
        val rows = board.size
        val cols = board[0].size

        val directions = arrayOf(intArrayOf(-1, -1), intArrayOf(-1, 0), intArrayOf(-1, 1), intArrayOf(0, -1), 
            intArrayOf(0, 1), intArrayOf(1, -1), intArrayOf(1, 0), intArrayOf(1, 1))

        for (i in 0 until rows) {
            for (j in 0 until cols) {
                var liveNeighbors = 0

                for (dir in directions) {
                    val newRow = i + dir[0]
                    val newCol = j + dir[1]

                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && (board[newRow][newCol] == 1 || board[newRow][newCol] == -1)) {
                        liveNeighbors++
                    }
                }

                if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[i][j] = -1
                }
                
                if (board[i][j] == 0 && liveNeighbors == 3) {
                    board[i][j] = 2
                }
            }
        }

        for (i in 0 until rows) {
            for (j in 0 until cols) {
                if (board[i][j] == -1) {
                    board[i][j] = 0
                } else if (board[i][j] == 2) {
                    board[i][j] = 1
                }
            }
        }
    }
}

                                            
class Solution {
  void gameOfLife(List<List<int>> board) {
    List<List<int>> copyBoard = List.generate(board.length, (index) => List<int>.filled(board[0].length, 0));

    for (int i = 0; i < board.length; i++) {
      for (int j = 0; j < board[0].length; j++) {
        int liveNeighbours = _countLiveNeighbours(board, i, j);

        if (board[i][j] == 1) {
          if (liveNeighbours < 2 || liveNeighbours > 3) {
            copyBoard[i][j] = 0;
          } else {
            copyBoard[i][j] = 1;
          }
        } else {
          if (liveNeighbours == 3) {
            copyBoard[i][j] = 1;
          } else {
            copyBoard[i][j] = 0;
          }
        }
      }
    }

    for (int i = 0; i < board.length; i++) {
      for (int j = 0; j < board[0].length; j++) {
        board[i][j] = copyBoard[i][j];
      }
    }
  }

  int _countLiveNeighbours(List<List<int>> board, int row, int col) {
    int count = 0;
    List<List<int>> directions = [
      [-1, -1], [-1, 0], [-1, 1],
      [0, -1], [0, 1],
      [1, -1], [1, 0], [1, 1]
    ];

    for (var dir in directions) {
      int newRow = row + dir[0];
      int newCol = col + dir[1];

      if (newRow >= 0 && newRow < board.length && newCol >= 0 && newCol < board[0].length) {
        if (board[newRow][newCol] == 1) {
          count++;
        }
      }
    }

    return count;
  }
}

                                            
func gameOfLife(board [][]int) {
    if len(board) == 0 || len(board[0]) == 0 {
        return
    }

    m, n := len(board), len(board[0])
    directions := []int{-1, 0, 1}

    getNextState := func(i, j int) int {
        liveNeighbours := 0
        for _, dx := range directions {
            for _, dy := range directions {
                if dx == 0 && dy == 0 {
                    continue
                }
                newRow, newCol := i+dx, j+dy
                if newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && (board[newRow][newCol] == 1 || board[newRow][newCol] == 2) {
                    liveNeighbours++
                }
            }
        }

        if board[i][j] == 1 {
            if liveNeighbours < 2 || liveNeighbours > 3 {
                return 2
            }
        } else {
            if liveNeighbours == 3 {
                return -1
            }
        }

        return board[i][j]
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            board[i][j] = getNextState(i, j)
        }
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] == -1 {
                board[i][j] = 1
            } else if board[i][j] == 2 {
                board[i][j] = 0
            }
        }
    }
}

                                            
object Solution {
    def gameOfLife(board: Array[Array[Int]]): Unit = {
        val m = board.length
        val n = board(0).length

        val directions = List((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))

        def countLiveNeighbors(x: Int, y: Int): Int = {
            var count = 0
            for ((dx, dy) <- directions) {
                val newX = x + dx
                val newY = y + dy
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && (board(newX)(newY) == 1 || board(newX)(newY) == -1))
                    count += 1
            }
            count
        }

        for (i <- 0 until m; j <- 0 until n) {
            val liveNeighbors = countLiveNeighbors(i, j)
            if (board(i)(j) == 1 && (liveNeighbors < 2 || liveNeighbors > 3))
                board(i)(j) = -1
            if (board(i)(j) == 0 && liveNeighbors == 3)
                board(i)(j) = 2
        }

        for (i <- 0 until m; j <- 0 until n) {
            if (board(i)(j) == -1)
                board(i)(j) = 0
            if (board(i)(j) == 2)
                board(i)(j) = 1
        }
    }
}

                                            
impl Solution {
    pub fn game_of_life(board: &mut Vec<Vec<i32>>) {
        let m = board.len();
        let n = board[0].len();
        
        let mut new_board = vec![vec![0; n]; m];
        
        let directions = vec![-1, 0, 1];
        
        for i in 0..m {
            for j in 0..n {
                let mut live_neighbors = 0;
                
                for &di in directions.iter() {
                    for &dj in directions.iter() {
                        if di == 0 && dj == 0 {
                            continue;
                        }
                        
                        let ni = i as i32 + di;
                        let nj = j as i32 + dj;
                        
                        if ni >= 0 && ni < m as i32 && nj >= 0 && nj < n as i32 {
                            live_neighbors += board[ni as usize][nj as usize];
                        }
                    }
                }
                
                if board[i][j] == 1 {
                    if live_neighbors < 2 || live_neighbors > 3 {
                        new_board[i][j] = 0;
                    } else {
                        new_board[i][j] = 1;
                    }
                } else {
                    if live_neighbors == 3 {
                        new_board[i][j] = 1;
                    } else {
                        new_board[i][j] = 0;
                    }
                }
            }
        }
        
        *board = new_board;
    }
}

To solve this coding challenge, we need to implement Conway's Game of Life on a given m x n grid. The game progresses by simultaneously applying a set of rules to every cell in the grid to determine its next state. Here's a detailed walkthrough of how to solve this problem.

Explanation

Problem Analysis

The Game of Life is a zero-player game where the evolution of the game is determined by its initial state. Each cell on the board can be either live (represented by a 1) or dead (represented by a 0). The cells interact with their eight neighbors based on a set of rules which govern the next state of each cell. The rules are:

Any live cell with fewer than two live neighbors dies (under-population).
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies (over-population).
Any dead cell with exactly three live neighbors becomes a live cell (reproduction).

The challenge is to compute the next state of the board by applying these rules simultaneously to every cell.

Constraints

The input board is a 2D array of size m x n.
Each cell in the board is either 0 (dead) or 1 (live).
The board needs to be updated in-place.
The board may be bounded, and handling edge cells can be tricky.

Plan

Iterate through each cell in the board, and count the number of live neighbors for each cell.
Apply the game rules to determine the next state of the cell:

Utilize temporary states to distinguish between current and next state updates without affecting the neighbor counting logic (e.g., mark cells with specific intermediate values like -1 or 2).

Finally, update the board to reflect the next state, converting intermediate values back to standard states.

Step-by-Step Implementation in Pseudocode

Initialize Variables

                                            
# direction vectors for the 8 neighbors (horizontal, vertical, diagonal)
neighbors = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

# determine number of rows and columns
rows = number of rows in board
cols = number of columns in board

First Pass: Determine New States with Temporary Markers

                                            
# Iterate through each cell in the board
for row_index from 0 to (rows - 1):
for col_index from 0 to (cols - 1):

# Initialize live neighbor counter
live_neighbors = 0

# Check all 8 neighbors
for direction in neighbors:
neighbor_row = row_index + direction[0]
neighbor_col = col_index + direction[1]

# Count live neighbors (abs is used to handle temporary markers)
if 0 <= neighbor_row < rows and 0 <= neighbor_col < cols:
if abs(board[neighbor_row][neighbor_col]) == 1:
live_neighbors += 1

# Apply game rules
# Rule 1 or Rule 3: live cell with <2 or >3 live neighbors dies
if board[row_index][col_index] == 1 and (live_neighbors < 2 or live_neighbors > 3):
board[row_index][col_index] = -1 # Mark as dead

# Rule 4: dead cell with 3 live neighbors becomes a live cell
if board[row_index][col_index] == 0 and live_neighbors == 3:
board[row_index][col_index] = 2 # Mark as live

Second Pass: Finalize Updates

                                            
# Iterate through each cell again to finalize state changes
for row_index from 0 to (rows - 1):
for col_index from 0 to (cols - 1):
# Update cell state based on temporary markers
if board[row_index][col_index] > 0:
board[row_index][col_index] = 1 # Finalize as live cell
else:
board[row_index][col_index] = 0 # Finalize as dead cell

Detailed Steps in Pseudocode

Initialization :

Define the possible directions to inspect neighboring cells.
Calculate the number of rows and columns in the board.

First Pass - Apply Rules with Temporary Markers :

Use nested loops to iterate through each cell in the board.
For each cell, count the number of live neighbors by checking all 8 directions.
Apply the Game of Life rules while using temporary markers to avoid conflict (e.g., marking future dead cells as -1 and future live cells as 2).

Second Pass - Finalize Board State :

Another set of nested loops to convert the temporary markers back to final states: -1 becomes 0 and 2 becomes 1.

By following this structured approach, we can ensure that all cells are updated simultaneously while retaining the integrity of the neighbor count calculation. This method guarantees an efficient and in-place solution to the Game of Life on a bounded 2D board.