LeetCode 289: Game of Life
Problem Description
Explanation
The problem requires updating the given board based on the rules of the Game of Life. We need to update the board in-place, considering the next state of each cell simultaneously. To do this, we can follow the following steps:
- Iterate through each cell in the board and calculate the number of live neighbors for each cell.
- Based on the current state of the cell and the number of live neighbors, update the cell to its next state according to the rules.
- To avoid updating cells and then using the updated values to update other cells, we can encode the next state in a different way. For example, we can use additional bits to represent the next state.
Time complexity: O(m*n) where m is the number of rows and n is the number of columns in the board. Space complexity: O(1) as we are updating the board in-place without using any additional data structures.
Solutions
class Solution {
public void gameOfLife(int[][] board) {
int m = board.length;
int n = board[0].length;
int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int liveNeighbors = 0;
for (int[] dir : directions) {
int x = i + dir[0];
int y = j + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] == 1 || board[x][y] == 2)) {
liveNeighbors++;
}
}
if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
board[i][j] = 2; // cell dies
} else if (board[i][j] == 0 && liveNeighbors == 3) {
board[i][j] = 3; // cell becomes live
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = board[i][j] % 2;
}
}
}
}Related LeetCode Problems
Loading editor...