Skip to main content

26. Game of Life

mediumAsked at Roblox

Simulate one generation of Conway's Game of Life on a 2D board using in-place state encoding — a direct parallel to how Roblox's voxel engine computes next-tick block states for physics simulations across large terrain grids.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an m x n binary grid board where 1 = live cell and 0 = dead cell, apply the Game of Life rules simultaneously to every cell and return the next state in-place. Rules: (1) live cell with <2 live neighbors dies; (2) live cell with 2–3 live neighbors survives; (3) live cell with >3 live neighbors dies; (4) dead cell with exactly 3 live neighbors becomes alive.

Constraints

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

Examples

Example 1

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

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

Approaches

1. Brute force — copy grid first

Copy the entire board, then apply rules reading from the copy and writing to the original. O(m*n) time, O(m*n) extra space for the copy.

Time
O(m*n)
Space
O(m*n)
function gameOfLife(board) {
  const rows = board.length, cols = board[0].length;
  const copy = board.map(row => [...row]);
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      let live = 0;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && copy[nr][nc] === 1) live++;
      }
      if (copy[r][c] === 1) {
        board[r][c] = (live === 2 || live === 3) ? 1 : 0;
      } else {
        board[r][c] = live === 3 ? 1 : 0;
      }
    }
  }
}

Tradeoff:

2. Optimal — in-place two-bit encoding

Encode transition states using extra bits: 2 = was live, now dead; 3 = was dead, now live. After applying rules, mask each cell to its final state. O(1) extra space.

Time
O(m*n)
Space
O(1)
function gameOfLife(board) {
  const rows = board.length, cols = board[0].length;
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      let live = 0;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && (board[nr][nc] & 1) === 1) live++;
      }
      if ((board[r][c] & 1) === 1 && (live === 2 || live === 3)) {
        board[r][c] |= 2; // was live, stays live
      } else if ((board[r][c] & 1) === 0 && live === 3) {
        board[r][c] |= 2; // was dead, becomes live
      }
    }
  }

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

Tradeoff:

Roblox-specific tips

Roblox often uses this problem as a litmus test for spatial simulation reasoning. The two-bit encoding trick is the answer they're looking for — it demonstrates you can work within memory constraints the way a game engine must when updating thousands of cells per tick. If the board is infinite (e.g., a Roblox infinite terrain), be ready to discuss sparse-grid representations using a HashMap of live cells instead.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Game of Life and other Roblox interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →