Game of Life

Share

Given a board with live (1) and dead (0) cells, apply Conway's Game of Life rules simultaneously: dead→live if exactly 3 live neighbors; live stays if 2 or 3 live neighbors; else live→dead.

Example 1
Input: [[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]]

Solution Approach

Use extra states: 2 = was alive now dead, 3 = was dead now alive. First pass marks changes, second pass finalizes.

  • For each cell: count live neighbors (state==1 or state==2).
  • If live and neighbors not 2 or 3: mark as 2 (dying).
  • If dead and exactly 3 live neighbors: mark as 3 (reviving).
  • Second pass: 2→0, 3→1.
Java
class Solution {
    public void gameOfLife(int[][] board) {
        int m=board.length, n=board[0].length;
        int[] d = {-1,0,1};
        for (int i=0;i<m;i++) for (int j=0;j<n;j++) {
            int live=0;
            for (int di:d) for (int dj:d) {
                if (di==0&&dj==0) continue;
                int r=i+di, c=j+dj;
                if (r>=0&&r<m&&c>=0&&c<n&&(board[r][c]==1||board[r][c]==2)) live++;
            }
            if (board[i][j]==1&&(live<2||live>3)) board[i][j]=2;
            else if (board[i][j]==0&&live==3) board[i][j]=3;
        }
        for (int i=0;i<m;i++) for (int j=0;j<n;j++) {
            if (board[i][j]==2) board[i][j]=0;
            else if (board[i][j]==3) board[i][j]=1;
        }
    }
}
  • Time Complexity: O(M*N)
  • Space Complexity: O(1)