Top Interview 150

The Game of Life problem is a simulation-based challenge involving matrix updates and in-place operations. Let’s solve LeetCode 289: Game of Life while ensuring the board is updated simultaneously, as required.

🚀 Problem Description

Given an m×n grid representing a board, where:

• 1: A cell is live.
• 0: A cell is dead.

The rules to determine the next state of the board are:

1. Any live cell with fewer than two live neighbors dies (underpopulation).
2. Any live cell with two or three live neighbors lives.
3. Any live cell with more than three live neighbors dies (overpopulation).
4. Any dead cell with exactly three live neighbors becomes live (reproduction).

The challenge: Update the board in place to reflect its next state.

💡 Examples

Example 1

Input: board = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]  
Output: [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]

Example 2

Input: board = [[1, 1], [1, 0]]  
Output: [[1, 1], [1, 1]]

🏆 JavaScript Solution

To update the board in place while maintaining the original state for simultaneous updates, we use state encoding:

• Intermediate States:
  • 2: A cell was live but will become dead.
  • 3: A cell was dead but will become live.

Implementation

var gameOfLife = function(board) {
    const rows = board.length;
    const cols = board[0].length;

    const countLiveNeighbors = (row, col) => {
        let liveCount = 0;
        const directions = [
            [-1, -1], [-1, 0], [-1, 1],
            [0, -1],         [0, 1],
            [1, -1], [1, 0], [1, 1],
        ];

        for (const [dr, dc] of directions) {
            const r = row + dr, c = col + dc;
            if (r >= 0 && r < rows && c >= 0 && c < cols && (board[r][c] === 1 || board[r][c] === 2)) {
                liveCount++;
            }
        }

        return liveCount;
    };

    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            const liveNeighbors = countLiveNeighbors(row, col);

            if (board[row][col] === 1) {
                if (liveNeighbors < 2 || liveNeighbors > 3) {
                    board[row][col] = 2; // Live -> Dead
                }
            } else {
                if (liveNeighbors === 3) {
                    board[row][col] = 3; // Dead -> Live
                }
            }
        }
    }

    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (board[row][col] === 2) {
                board[row][col] = 0; // Live -> Dead
            } else if (board[row][col] === 3) {
                board[row][col] = 1; // Dead -> Live
            }
        }
    }
};

🔍 How It Works

1. Count Live Neighbors:

   • Use an array of 8 directions to check all neighboring cells for live states (1 or 2).

2. Encode Intermediate States:

   • 2: A cell transitions from live to dead.
   • 3: A cell transitions from dead to live.

3. Finalize Updates:

   • Traverse the matrix again to convert 2→0 and 3→1.

🔑 Complexity Analysis

• Time Complexity: O(m⋅n), where m is the number of rows and n is the number of columns.

  • Each cell is visited twice: once to apply rules and once to finalize updates.

• Space Complexity: O(1), as the updates are performed in place.

📋 Dry Run

Input: board = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]

Output: [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]

✨ Pro Tips for Interviews

1. Explain Intermediate States:

   • Highlight how encoding states avoids dependency issues during simultaneous updates.

2. Edge Cases:

   • Single-row or single-column boards. Boards where all cells are live or all cells are dead.

3. Follow-Up:

   • For infinite boards, consider tracking only the active area (cells with live neighbors).

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Set Matrix Zeroes - JavaScript Solution

What’s your preferred method to solve this problem? Let’s discuss! 🚀