• 36.5%

https://leetcode.com/problems/game-of-life/#/description

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population..
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

https://discuss.leetcode.com/topic/26112/c-o-1-space-o-mn-time

C++ O(1) space, O(mn) time

Since the board has ints but only the 1-bit is used, I use the 2-bit to store the new state. At the end, replace the old state with the new state by shifting all values one bit to the right.

Note that the above count counts the live ones among a cell’s neighbors and the cell itself. Starting with int count = -board[i][j] counts only the live neighbors and allows the neat

test. Thanks to aileenbai for showing that one in the comments.

https://discuss.leetcode.com/topic/26176/c-ac-code-o-1-space-o-mn-time

C++ AC Code O(1) space, O(mn) time

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

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.

And here’s a wrapper that uses the above infinite board solution to solve the problem we have here at the OJ (submitted together, this gets accepted):

https://discuss.leetcode.com/topic/27167/c-o-mn-time-o-1-space-sol

C++ O(mn)-time, O(1)-space sol

First this solution does not involve bit-manipulation and only involves addition of integers.

The idea is to go through the matrix from top-left corner to the bottom-right corner, and check only 4 cells (“accumulate” scores “for both cells” if the other cell is originally a 1). Graphically speaking, it is like this:

where the @ cell is the one that you are working on, 0 cells are those you have gone through (don’t work on them again!), and the X cells are those you have not gone through and should work on. For example, if one X cell is originally a 1, you should add C (a constant) to @ cell, and simultaneously if @ cell is originally a 1, you add C to that X cell.

The constant C can be 2. If it is 2 then when you will find that after done working on the current cell if it’s value is 5 or 7 (cell @ is originally a 1 and have 2 or 3 neighbours) or 6 (cell @ is originally a 0 and have 3 neighbours), then you should reset it to be 1 (live), otherwise reset it to be zero (dead). And when accumulating scores, you know a cell is originally a 1 if it has odd-numbered score, and it is originally a 0 if it has even-numbered score. The code is

https://discuss.leetcode.com/topic/27098/python-solution-easy-to-understand

Python solution, easy to understand..

https://discuss.leetcode.com/topic/26117/ac-python-40-ms-solution-o-mn-time-o-1-extra-space

AC Python 40 ms solution O(mn) time O(1) extra space

Everyone knows how to update this board if another m * n array is allowed. The O(1) space solution is just using the wasted bits in the original array. Instead of only 0 and 1 we now need the second bit for the updated value. The living condition is just by definition.

Of course, writing everything together will save several lines of code. However, implement things like this, readability and expandability counts.

As of the follow up question.
For example your 3 * 3 initial board is the following:

In the case of only 3 * 3 the next generation is:

However in the case of a infinite board the next generation is:

Question is how to you implement this expandable board. One solution of the infinity situation is using a upper level grid, a grid of grids, instead of only one grid of cells. Note that we can be lazy. We only initialize (allocate the memory for real) a certain grid if any cell in it is activated. The rest of the unused grid can be pointer only.

1ms, 11.45%, October 18, 2016

https://discuss.leetcode.com/topic/29054/easiest-java-solution-with-explanation