# 289. Game of Life

• Time: $O(mn)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public: void gameOfLife(vector>& board) { const int m = board.size(); const int n = board[0].size(); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { int ones = 0; for (int x = max(0, i - 1); x < min(m, i + 2); ++x) for (int y = max(0, j - 1); y < min(n, j + 2); ++y) ones += board[x][y] & 1; // any live cell with 2 or 3 live neighbors // lives on to the next generation if (board[i][j] == 1 && (ones == 3 || ones == 4)) board[i][j] |= 0b10; // any dead cell with exactly 3 live neighbors // becomes a live cell, as if by reproduction if (board[i][j] == 0 && ones == 3) board[i][j] |= 0b10; } for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) board[i][j] >>= 1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public void gameOfLife(int[][] board) { final int m = board.length; final int n = board[0].length; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { int ones = 0; for (int x = Math.max(0, i - 1); x < Math.min(m, i + 2); ++x) for (int y = Math.max(0, j - 1); y < Math.min(n, j + 2); ++y) ones += board[x][y] & 1; // any live cell with 2 or 3 live neighbors // lives on to the next generation if (board[i][j] == 1 && (ones == 3 || ones == 4)) board[i][j] |= 0b10; // any dead cell with exactly 3 live neighbors // becomes a live cell, as if by reproduction if (board[i][j] == 0 && ones == 3) board[i][j] |= 0b10; } for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) board[i][j] >>= 1; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution: def gameOfLife(self, board: List[List[int]]) -> None: m = len(board) n = len(board[0]) for i in range(m): for j in range(n): ones = 0 for x in range(max(0, i - 1), min(m, i + 2)): for y in range(max(0, j - 1), min(n, j + 2)): ones += board[x][y] & 1 # any live cell with 2 or 3 live neighbors # lives on to the next generation if board[i][j] == 1 and (ones == 3 or ones == 4): board[i][j] |= 0b10 # any dead cell with exactly 3 live neighbors # becomes a live cell, as if by reproduction if board[i][j] == 0 and ones == 3: board[i][j] |= 0b10 for i in range(m): for j in range(n): board[i][j] >>= 1