The O(n) Club: Game of Life—When State Mutations Attack

The O(n) Club: Game of Life—When State Mutations Attack

⚡ TL;DR

Game of Life: the code simulation where cells live, die, or rise from the dead—according to rules that sound like HR policies but somehow generate digital art. Naive way? Duplicate the board every step—your CPU groans, your RAM sobs. Smart way? In-place updates with state markers. (Arrays rejoice!)

// Naive (please don't do this in real interviews)
int[][] next = new int[m][n];
for (int i = 0; i < m; i++)
  for (int j = 0; j < n; j++)
    next[i][j] = aliveNextStep(board, i, j);
// Overwrite 'board' with 'next'

🧠 How Devs Usually Mess This Up

Everybody’s first try: update cells as you go, turning neighbors into zombies before they can vote. Congrats: your neighbor counts are now as honest as a crypto scam, because overwriting values mid-sweep wrecks the whole “simultaneous update” thing. Plus, let your access go one cell out-of-bounds and Java’s IndexOutOfBoundsException will drop the hammer like Thor on a Monday.

🔍 What’s Actually Going On

Picture the grid as a very toxic open office. Each cell (employee) consults its neighboring cubicles, then instantly decides: keep existing, burn out, or randomly “appear” through a mysterious hiring process (all based on their eight closest colleagues). The catch: all these choices lock in at the same instant, because nobody wants to see one person’s fate leaking into another’s before the meeting is adjourned.

The trick? Sneaky Post-its a.k.a. encoded numbers (hello, 2 and -1). After marking each cell’s fate, do a second sweep to finalize their new states. Welcome to state encoding: like regular gossip, but more organized.

🛠️ PseudoCode

• Scan each cell: Count live neighbors (in all 8 directions, diagonals included—no discrimination here).

  // Count neighbors
  grid bounds = your best friend
  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      int live = countLiveNeighbors(board, i, j);

• Mark transitions, don’t overwrite yet:
  • If cell was alive (1) and should die: set to 2 (RIP, but not yet official)
  • If cell was dead (0) and should come to life: set to -1 (zombie mode)

  // In-place marking
  if (board[i][j] == 1 && (live < 2 || live > 3)) board[i][j] = 2;
  if (board[i][j] == 0 && live == 3) board[i][j] = -1;

• Second sweep: Finalize by turning 2 → 0 and -1 → 1 (normalizing states).

💻 The Code

public class GameOfLife {
    private static final int[] DX = {-1, -1, -1,  0, 0, 1, 1, 1};
    private static final int[] DY = {-1,  0,  1, -1, 1,-1, 0, 1};
    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 = 0;
                for (int d = 0; d < 8; d++) {
                    int ni = i + DX[d], nj = j + DY[d];
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                        if (Math.abs(board[ni][nj]) == 1) 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++)
                board[i][j] = (board[i][j] == 2) ? 0 : (board[i][j] == -1 ? 1 : board[i][j]);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Stay in bounds: Neighbor checks need if-guards. Or else: exception city.
• Simultaneous updates = double sweep: Use encoded markers during the first pass, then sweep again. If you do it in one go, your logic will eat itself.
• Space/Time: Time: O(m*n). Space: O(1) if you do it right. But if you cowardly copy grids, that’s double space. (Interviewers notice.)
• When visualizing: Dead cells sometimes look livelier than you after three coffees. Double check your “live” colors.

🧠 Interviewer Brain-Tattoo

“If you update mid-pass, you’re not playing the Game of Life—you’re playing Whack-a-Bug.”