**Solution**

**Game of Life** https://leetcode.com/problems/game-of-life/

**Brute Force - Not in-place solution**

Solution 1 we maintain a list of co-ordinates which must be inverted for next round. This is not an inplace solution.

```
class Solution(object):
def nbr_process(self, x, y, board):
M, N = len(board), len(board[0])
candidate, live = [(x,y-1), (x,y+1), (x-1,y), (x+1,y), (x-1,y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1)], 0
for x1,y1 in candidate:
if 0<=x1<M and 0<=y1<N and board[x1][y1] == 1:
live += 1
return live
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: void Do not return anything, modify board in-place instead.
"""
M, N = len(board), len(board[0])
result = []
for i in range(M):
for j in range(N):
live = self.nbr_process(i,j,board)
if board[i][j] == 1 and (live < 2 or live > 3):
result.append((i,j))
if board[i][j] == 0 and live == 3:
result.append((i,j))
for a,b in result:
board[a][b] = board[a][b] ^ 1
return
```

**Optimized In-place Solution**

Solution 2 we mark the inverted nodes with 2 and 3 which signify a meaning for this life and consequence in next life.

```
class Solution(object):
def nbr_process(self, x, y, board):
M, N = len(board), len(board[0])
candidate, live = [(x,y-1), (x,y+1), (x-1,y), (x+1,y), (x-1,y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1)], 0
for x1,y1 in candidate:
if 0<=x1<M and 0<=y1<N and (board[x1][y1] == 1 or board[x1][y1] == 2):
live += 1
return live
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: void Do not return anything, modify board in-place instead.
"""
M, N = len(board), len(board[0])
for i in range(M):
for j in range(N):
live = self.nbr_process(i,j,board)
if board[i][j] == 1 and (live < 2 or live > 3):
board[i][j] = 2 # 2 means it is alive now but will be dead next round
if board[i][j] == 0 and live == 3:
board[i][j] = 3 # 3 means it is dead now but will be alive next round
for i in range(M):
for j in range(N):
if board[i][j] == 2:
board[i][j] = 0
if board[i][j] == 3:
board[i][j] = 1
return
```

https://discuss.leetcode.com/topic/26236/infinite-board-solution

*For the second follow-up question, here's a solution for an infinite board. Instead of a two-dimensional array of ones and zeros, I represent the board as a set of live cell coordinates.*