algoadvance

Leetcode 289. Game of Life

Problem Statement

The “Game of Life,” also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 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.

The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

Clarifying Questions

  1. Can the modifications be made directly to the input board, or should a new board be created?
    • We’ll modify the input board in-place without using additional space.
  2. What are the constraints on the board dimensions?
    • Constraints are not strictly specified, but the problem should be solved efficiently for reasonably sized boards.
  3. Are the board boundaries wrapped around like a toroidal array?
    • No, the edges and corners do not wrap around.

Code

Here is the C++ code to solve the problem:

#include <vector>
using namespace std;

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        if (board.empty() || board[0].empty()) return;
        
        int m = board.size();
        int n = board[0].size();
        
        // Make a copy of the original board to check the previous state
        vector<vector<int>> copy = board;
        
        // Directions array for the eight neighbors
        vector<int> directions = {0, 1, -1};
        
        for (int row = 0; row < m; ++row) {
            for (int col = 0; col < n; ++col) {
                int liveNeighbors = 0;
                
                // Check all eight neighbors
                for (int i = 0; i < 3; ++i) {
                    for (int j = 0; j < 3; ++j) {
                        if (directions[i] == 0 && directions[j] == 0) continue;
                        
                        int r = row + directions[i];
                        int c = col + directions[j];
                        
                        // Check the validity of cell and whether it was originally a live cell
                        if ((r < m && r >= 0) && (c < n && c >= 0) && (copy[r][c] == 1)) {
                            ++liveNeighbors;
                        }
                    }
                }
                
                // Apply the Game of Life rules to determine the new state of the cell
                if (copy[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[row][col] = 0; // Rule 1 or Rule 3
                } else if (copy[row][col] == 0 && liveNeighbors == 3) {
                    board[row][col] = 1; // Rule 4
                }
            }
        }
    }
};

Strategy

  1. Copy the Board: Create a copy of the board to check the original state of each cell because all updates need to be simultaneous.
  2. Neighbor Check: For every cell, count the number of live neighbors by inspecting all eight possible positions around the cell.
  3. Rule Application: Apply the four defined rules using the count of live neighbors.
    • Rule 1 and Rule 3: Live cell dies if under-populated or over-populated.
    • Rule 2: Live cell with 2 or 3 live neighbors continues to live (no action needed as it stays the same).
    • Rule 4: Dead cell with exactly 3 live neighbors becomes a live cell.

Time Complexity

The solution iterates over all cells exactly once, and for each cell, it checks its eight neighbors. Therefore, the time complexity is:

The space complexity is O(m * n) due to the use of a duplicate board.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI