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.
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]]
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.
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)