Leetcode 289 Game of Life
The most intuitive solution would be to go over each cell of the board, base on its neighbors, record the new value in a temporary board. Then after all cells are done, we loop through the original board again and update the value base on the temporary board. This solution is straight forward but does require extra space O(mn). The best solution can be done with no extra space.
The reason why we need extra space in the first place is because we need to store the new value of each cell. Instead of storing the info in another matrix. We can simply use the existing cell to store the new value, but in a different flavor. The board only contains 0’s and 1’s, we can map the new value according the following rules. e.g if the original value is 0 and the new value should be 1, we write 2 as the new value.
// map between the number transition and the new int value
// 0 -> 0 : 2
// 0 -> 1 : 3
// 1 -> 0 : 4
// 1 -> 1 : 5To easily look up both the original value and new value base on the temporary value, we need a reversed version of the map, something like below. e.g given 2, I would know the original value of the cell is 0 and the new value should be 0.
let reverseMap = {
2: '00',
3: '01',
4: '10',
5: '11',
0: '0',
1: '1'
}Solution
/**
* @param {number[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var gameOfLife = function(board) {
// map between the number transition and the new int value
// 0 -> 0 : 2
// 0 -> 1 : 3
// 1 -> 0 : 4
// 1 -> 1 : 5
let reverseMap = {
2: '00',
3: '01',
4: '10',
5: '11',
0: '0',
1: '1'
}
const getOriginalValueFromMap = (v) => {
return parseInt(reverseMap[v].toString().split('')[0])
}
const getNewlValueFromMap = (v) => {
return parseInt(reverseMap[v].split('')[1])
}
const getNewValueForCell = (i, j) => {
let ones = 0;
for(let x = i - 1; x <= i + 1; x++) {
for(let y = j - 1; y <= j + 1; y++) {
if(x >= 0 && y >=0 && x < board.length && y < board[0].length && (x !== i || y !== j)) {
if(getOriginalValueFromMap(board[x][y])) {
ones++;
}
}
}
}
if(board[i][j]) {
if(ones < 2 || ones > 3) {
return 4
} else {
return 5
}
} else {
if(ones === 3) {
return 3
} else {
return 2
}
}
}
for(let i = 0; i < board.length; i++) {
for(let j = 0; j < board[0].length; j++) {
board[i][j] = getNewValueForCell(i, j)
}
}
for(let i = 0; i < board.length; i++) {
for(let j = 0; j < board[0].length; j++) {
board[i][j] = getNewlValueFromMap(board[i][j])
}
}
};Time Complexity:
O(nm)
Space Complexity:
O(1)