What is the time complexity of Game of Life?

The optimal solution has a time complexity of O(m*n).

What data structures are used to solve Game of Life?

This problem uses Array, Matrix, Simulation. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Game of Life?

Insight 1: The core challenge is updating the board in-place while ensuring changes don't affect other cells in the same generation's calculation. Using additional space to store the next state would be straightforward but violates the in-place requirement. Insight 2: The solution uses bit manipulation to store the next state alongside the current state within the same cell. This is achieved by using the 2nd bit (value 2) of each cell to represent the next state.

Which companies ask LeetCode 289. Game of Life in interviews?

This problem is frequently asked at Anduril, BitGo, Cloudflare, Dropbox, Google and 3 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Game of Life - LeetCode 289 Solution

Game of Life - Complete Solution Guide

Game of Life is LeetCode problem 289, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

According to 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." 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): Any live cell with fewer than tw

Detailed Explanation

The Game of Life is a cellular automaton where cells in a grid evolve based on a set of rules related to their neighbors. The input is a 2D array (board) representing the current state of the game, where '1' represents a live cell and '0' represents a dead cell. The task is to update the board in-place to its next state based on these rules: 1. A live cell with fewer than two live neighbors dies (underpopulation). 2. A live cell with two or three live neighbors lives on to the next generation. 3. A live cell with more than three live neighbors dies (overpopulation). 4. A dead cell with exactly three live neighbors becomes a live cell (reproduction). The board is updated simultaneously; that is, changes to one cell shouldn't affect calculations for another cell in the same step. The constraints include the dimensions of the board being between 1 and 25, and each cell being either 0 or 1.

Solution Approach

The provided solution updates the board in-place using bit manipulation. It iterates through each cell, counts the number of live neighbors, and then uses the rules to determine the cell's next state. Instead of directly updating the cell with 0 or 1, it encodes the next state in the second bit of the cell's value. After processing all cells, it shifts the bits to the right by one position, effectively updating the board with the next state.

Step-by-Step Algorithm

Step 1: Iterate through each cell (i, j) of the board.
Step 2: For each cell, iterate through its eight neighbors (including diagonals). Handle boundary conditions to avoid out-of-bounds access.
Step 3: Count the number of live neighbors for the current cell. Remember to only consider cells within bounds.
Step 4: Apply the Game of Life rules based on the current cell's state (live or dead) and the number of live neighbors: - If the cell is live (board[i][j] & 1 == 1): - If live_neighbors is 2 or 3, mark the cell to live in the next state (board[i][j] |= 2). - If the cell is dead (board[i][j] & 1 == 0): - If live_neighbors is 3, mark the cell to live in the next state (board[i][j] |= 2).
Step 5: After processing all cells, iterate through the board again and update each cell's value by shifting its bits to the right by one position (board[i][j] >>= 1). This effectively moves the next state (stored in the second bit) to the first bit, updating the board.

Key Insights

Insight 1: The core challenge is updating the board in-place while ensuring changes don't affect other cells in the same generation's calculation. Using additional space to store the next state would be straightforward but violates the in-place requirement.
Insight 2: The solution uses bit manipulation to store the next state alongside the current state within the same cell. This is achieved by using the 2nd bit (value 2) of each cell to represent the next state.
Insight 3: Careful iteration through the neighbors of each cell and boundary condition checks are crucial for correctly applying the rules.

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(1)

Topics

This problem involves: Array, Matrix, Simulation.

Companies

Asked at: Anduril, BitGo, Cloudflare, Dropbox, Google, Snap, Two Sigma, Warnermedia.

Game of Life | LeetCode 289

Medium

Array Matrix Simulation

Time: O(m*n)Space: O(1)

Solution Code

Available in:

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live_neighbors = 0;
                for (int dr = -1; dr <= 1; dr++) {
                    for (int dc = -1; dc <= 1; dc++) {
                        if (dr == 0 && dc == 0) {
                            continue;
                        }

                        int r = i + dr;
                        int c = j + dc;

                        if (0 <= r && r < m && 0 <= c && c < n && (board[r][c] & 1) == 1) {
                            live_neighbors += 1;
                        }
                    }
                }

                if ((board[i][j] & 1) == 1) {
                    if (live_neighbors == 2 || live_neighbors == 3) {
                        board[i][j] |= 2;
                    }
                } else {
                    if (live_neighbors == 3) {
                        board[i][j] |= 2;
                    }
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] >>= 1;
            }
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 289: Game of Life - Detailed explanation and solution approaches.

Topics

Array Matrix Simulation

Companies

AndurilBitGoCloudflareDropboxGoogleSnapTwo SigmaWarnermedia

Stats

Difficulty:Medium

Languages:4

Companies:8

Problem #:289

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Iterate through each cell (i, j) of the board.
2
Step 2: For each cell, iterate through its eight neighbors (including diagonals). Handle boundary conditions to avoid out-of-bounds access.
3
Step 3: Count the number of live neighbors for the current cell. Remember to only consider cells within bounds.
4
Step 4: Apply the Game of Life rules based on the current cell's state (live or dead) and the number of live neighbors: - If the cell is live (board[i][j] & 1 == 1): - If live_neighbors is 2 or 3, mark the cell to live in the next state (board[i][j] |= 2). - If the cell is dead (board[i][j] & 1 == 0): - If live_neighbors is 3, mark the cell to live in the next state (board[i][j] |= 2).
5
Step 5: After processing all cells, iterate through the board again and update each cell's value by shifting its bits to the right by one position (board[i][j] >>= 1). This effectively moves the next state (stored in the second bit) to the first bit, updating the board.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is determined by the nested loops that iterate through each cell in the m x n board. For each cell, a constant amount of work is performed to count neighbors. The space complexity is constant because the algorithm modifies the input array in-place and doesn't allocate significant additional memory.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using an auxiliary matrix

Create a separate matrix of the same dimensions as the board to store the next state. Calculate the next state based on the current state of the board and store it in the auxiliary matrix. Finally, copy the auxiliary matrix back to the board.

Time: O(m*n)Space: O(m*n)

Trade-offs: This approach is simpler to understand but uses O(m*n) extra space, violating the in-place constraint. It is easier to implement but less efficient than the in-place solution.

✨

Key Insights

1Insight 1: The core challenge is updating the board in-place while ensuring changes don't affect other cells in the same generation's calculation. Using additional space to store the next state would be straightforward but violates the in-place requirement.
2Insight 2: The solution uses bit manipulation to store the next state alongside the current state within the same cell. This is achieved by using the 2nd bit (value 2) of each cell to represent the next state.
3Insight 3: Careful iteration through the neighbors of each cell and boundary condition checks are crucial for correctly applying the rules.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: Cells at the boundaries of the board. The solution correctly handles these cases by including a boundary check (0 <= r < m && 0 <= c < n) when counting neighbors. This ensures that the algorithm doesn't try to access cells outside the bounds of the array.
Edge case 2: A board with all live or all dead cells. The solution correctly applies the rules, and the simulation works as expected in these scenarios.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling boundary conditions correctly when counting neighbors. This can lead to array index out-of-bounds errors.

✗Common mistake 2: Updating the board directly while calculating the next state. This violates the requirement that updates must occur simultaneously and leads to incorrect results.

✗Common mistake 3: Forgetting to shift the bits after calculating the next states, resulting in the board not being properly updated to the next generation.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Cellular automata have applications in modeling complex systems such as traffic flow, forest fires, and the spread of diseases.

🏦Real-world scenario 2: Simulating the behavior of biological systems, such as the growth and development of organisms, can be achieved using cellular automata-like models.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 18, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Game of Life"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether matrix techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?