Game of Life (Encode States In-Place)

📋

Game of Life (Encode States In-Place)

Edge cases:

</>

IDE

def gameOfLife(board: list[list[int]]) -> None:public void gameOfLife(int[][] board)void gameOfLife(vector<vector<int>>& board)function gameOfLife(board)

def gameOfLife(board):
    # Write your solution here
    pass

class Solution {
    public void gameOfLife(int[][] board) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void gameOfLife(vector<vector<int>>& board) {
    // Write your solution here
}

function gameOfLife(board) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Cells updated greedily causing incorrect next statesUpdating cells in-place without encoding next state separately, causing neighbor counts to be incorrect✅ Encode next state in a separate bit or value before decoding all cells after processing

Wrong: Dead cells becoming live without exactly three live neighborsIncorrect application of reproduction rule or neighbor counting errors✅ Apply reproduction rule only when live_neighbors == 3; count neighbors correctly including diagonals

Wrong: Index out of bounds or incorrect neighbor counting at edgesNot checking boundaries before accessing neighbors✅ Add boundary checks for all neighbor indices before accessing board

Wrong: Diagonal neighbors ignored or miscountedCounting only orthogonal neighbors or misindexing diagonals✅ Include all 8 directions in neighbor counting loops

Wrong: Multiple updates per cell or confusion between 0/1 and unbounded updatesApplying rules multiple times or not encoding states properly✅ Use state encoding to store current and next states separately and update once after processing

✓

Test Cases

Focus on handling edge cases like empty boards and single cells correctly.

Watch out for common pitfalls like greedy updates and incorrect neighbor counting.

Optimize your solution to run efficiently on large boards within time limits.

t1_01basic

Input{"board":[[0,0,0],[0,0,1],[1,0,1],[0,1,1]]}

Expectednull

⏱ Performance - must finish in 2000ms

Each cell updates based on live neighbors; for example, the cell at (1,0) becomes live because it has exactly three live neighbors.

💡 Consider each cell's neighbors to determine its next state.

💡 Use the rules of underpopulation, survival, overpopulation, and reproduction carefully.

💡 Encode next state in-place using extra bits to avoid overwriting current state before processing all cells.

Why it failed: Incorrect next state encoding or decoding; likely overwriting current state before processing all cells. Fix by encoding next state in higher bits and decoding after processing all cells.

✓ Correctly encodes and decodes next state in-place.

t1_02basic

Input{"board":[[1,1,0],[1,1,0],[0,0,0]]}

Expectednull

⏱ Performance - must finish in 2000ms

Cells update according to neighbors; for example, cell (1,1) becomes live due to exactly three live neighbors.

💡 Count live neighbors for each cell before updating.

💡 Remember to apply all four rules for live and dead cells.

💡 Use a two-pass approach: first encode next state, then decode to finalize.

Why it failed: Failing to count neighbors correctly or applying rules incorrectly; fix neighbor counting and apply rules precisely with in-place encoding.

✓ Correct neighbor counting and in-place state update.

t2_01edge

Input{"board":[[0,0,0],[0,0,0],[0,0,0]]}

Expectednull

⏱ Performance - must finish in 2000ms

All cells dead remain dead as no reproduction occurs.

💡 Check behavior when no live neighbors exist.

💡 Ensure dead cells with zero neighbors do not become live.

💡 Confirm in-place encoding does not alter dead cells incorrectly.

Why it failed: Incorrectly changing dead cells without three live neighbors; fix by applying reproduction rule only when exactly three live neighbors.

✓ Dead cells remain dead correctly when no live neighbors.

t2_02edge

Input{"board":[[0]]}

Expectednull

⏱ Performance - must finish in 2000ms

Single live cell dies due to underpopulation (fewer than two live neighbors).

💡 Handle single cell boards carefully.

💡 Check neighbor counting does not access out-of-bounds indices.

💡 Apply underpopulation rule correctly for isolated live cells.

Why it failed: Failing to handle boundary cells or single cell boards; fix neighbor checks to avoid out-of-bounds and apply underpopulation rule.

✓ Single live cell dies correctly due to underpopulation.

t2_03edge

Input{"board":[[0,0,1,0,0]]}

Expectednull

⏱ Performance - must finish in 2000ms

One row board: edge cells die due to overpopulation or underpopulation, middle cells survive.

💡 Test boards with only one row or one column.

💡 Ensure neighbor counting handles edges correctly.

💡 Apply overpopulation and survival rules precisely for edge cells.

Why it failed: Incorrect neighbor counting at edges causing wrong cell updates; fix boundary checks and neighbor counting logic.

✓ One-row board updates correctly with proper edge neighbor handling.

t2_04edge

Input{"board":[[0],[0],[1],[0],[0]]}

Expectednull

⏱ Performance - must finish in 2000ms

One column board: edge cells die due to overpopulation or underpopulation, middle cells survive.

💡 Test boards with only one column.

💡 Ensure neighbor counting handles vertical edges correctly.

💡 Apply rules carefully for edge and middle cells.

Why it failed: Incorrect neighbor counting on vertical edges; fix boundary checks and neighbor counting logic.

✓ One-column board updates correctly with proper edge neighbor handling.

t3_01corner

Input{"board":[[1,0,1],[0,0,0],[1,0,1]]}

Expectednull

⏱ Performance - must finish in 2000ms

Tests correct handling of in-place encoding to avoid greedy update errors.

💡 Beware of updating cells greedily without preserving original states.

💡 Use bit manipulation or state encoding to store both current and next states.

💡 Decode all cells after processing to finalize the next state.

Why it failed: Greedy update overwrites current state before neighbor checks; fix by encoding next state separately and decoding after all updates.

✓ In-place encoding prevents greedy update errors.

t3_02corner

Input{"board":[[0,0,0],[0,0,0],[0,0,0]]}

Expectednull

⏱ Performance - must finish in 2000ms

Diagonal live cells die due to underpopulation; tests correct neighbor counting (no diagonal confusion).

💡 Ensure neighbor counting includes all 8 directions correctly.

💡 Do not confuse diagonal neighbors with orthogonal neighbors.

💡 Apply underpopulation rule correctly for isolated cells.

Why it failed: Incorrect neighbor counting ignoring diagonals or counting wrong neighbors; fix neighbor iteration to include all 8 directions.

✓ Correct neighbor counting including diagonals.

t3_03corner

Input{"board":[[0,0,0],[1,1,1],[0,0,0]]}

Expectednull

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded updates; only one update per cell allowed.

💡 Remember each cell updates once per generation.

💡 Avoid applying rules multiple times or accumulating states incorrectly.

💡 Use state encoding to track current and next states distinctly.

Why it failed: Applying updates multiple times or confusing 0/1 with unbounded updates; fix by encoding next state separately and updating once after processing all cells.

✓ Single update per cell with correct state encoding.

t4_01performance

Input{"board":[[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1],[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1],[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1],[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1],[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1],[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]]}

Expectednull

⏱ Performance - must finish in 2000ms

Large 100x100 board tests O(m*n) time complexity; brute force O(m*n) must complete within 2 seconds.

💡 Optimize neighbor counting to O(1) per cell.

💡 Use in-place state encoding to avoid extra space.

💡 Avoid nested loops beyond O(m*n) complexity.

Why it failed: TLE due to exponential or inefficient neighbor counting; fix by using O(m*n) DP or in-place encoding approach.

✓ Efficient O(m*n) solution passes within time limit.

Practice

1. You are given a matrix of integers. You need to find all elements that are the smallest in their row and simultaneously the largest in their column. Which approach guarantees an optimal solution to this problem?

easy

A. Use a brute force approach checking each element by scanning its entire row and column repeatedly.

B. Precompute the minimum value of each row and the maximum value of each column, then find elements matching both conditions in a single pass.

C. Apply a dynamic programming approach to store intermediate minimum and maximum values for submatrices.

D. Use a greedy approach by selecting the smallest element in each row and checking if it is the largest in its column.

Solution

1. Step 1: Understand problem constraints

   The problem requires identifying elements that are simultaneously the minimum in their row and maximum in their column.

2. Step 2: Evaluate approaches

   Brute force (A) is correct but inefficient. DP (C) is unnecessary overhead. Greedy (D) can fail if multiple minimums exist in a row but only one is maximum in its column. Precomputing row minimums and column maximums (B) allows a single pass to find all lucky numbers efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Precompute arrays then single pass -> optimal and correct [OK]

Hint: Precompute mins and maxes for single pass [OK]

Common Mistakes:

• Assuming greedy selection per row suffices
• Using DP unnecessarily
• Brute force is too slow

2. You are given an m x n matrix. If an element is 0, you must set its entire row and column to 0 in-place without using extra space proportional to the matrix size. Which approach guarantees an optimal solution with O(1) additional space?

easy

A. Use a greedy approach that zeroes rows and columns immediately when a zero is found during iteration.

B. Use a brute force approach by creating a separate matrix to mark zero positions and then update the original matrix.

C. Use dynamic programming to store zero positions and propagate zeroes through the matrix.

D. Use the first row and first column of the matrix as flags to mark which rows and columns should be zeroed, then update the matrix accordingly.

Solution

1. Step 1: Understand space constraints

   The problem requires in-place modification with O(1) extra space, so approaches using extra matrices or arrays are not optimal.

2. Step 2: Identify the flagging technique

   Using the first row and first column as markers allows tracking which rows and columns to zero without extra space, enabling a single pass update.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First row/column flagging is a classic O(1) space solution [OK]

Hint: Use matrix edges as flags to save space [OK]

Common Mistakes:

• Zeroing rows/columns immediately loses info about other zeros
• Using extra space arrays violates O(1) space constraint
• Greedy zeroing fails when zeros appear after initial zeroing

3. You are given a square matrix and asked to transform it so that rows become columns and columns become rows without using extra space. Which approach guarantees an optimal in-place solution?

easy

A. Use a brute force approach by creating a new matrix and copying elements accordingly.

B. Swap elements symmetrically across the diagonal only once, iterating over the upper triangle of the matrix.

C. Apply a greedy approach by swapping elements row-wise without considering the diagonal symmetry.

D. Use dynamic programming to store intermediate transposed states and build the final matrix.

Solution

1. Step 1: Understand the problem constraints

   The problem requires an in-place transpose of a square matrix, meaning no extra matrix can be used.

2. Step 2: Identify the correct approach

   Swapping elements symmetrically across the diagonal once (upper triangle only) ensures each pair is swapped exactly once, achieving in-place transpose efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping only upper triangle elements avoids double swaps and extra space [OK]

Hint: Swap only upper triangle elements once [OK]

Common Mistakes:

• Using extra space unnecessarily
• Swapping elements twice by iterating entire matrix
• Ignoring diagonal symmetry leading to incorrect results

4. Consider the following buggy code snippet for generating an n x n spiral matrix. Which line contains the subtle bug that can cause incorrect output or infinite loops?

medium

A. Line updating 'right' boundary after downward fill

B. Line after filling top row: missing update of 'top' boundary

C. Line updating 'bottom' boundary after leftward fill

D. Line updating 'left' boundary after upward fill

Solution

1. Step 1: Identify boundary updates after each direction

   After filling the top row (direction 0), the 'top' boundary must be incremented to avoid overwriting.

2. Step 2: Locate missing update

   The code comment indicates the 'top' boundary update is missing, causing the loop to overwrite the same row repeatedly or cause infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing 'top += 1' causes repeated writes to top row [OK]

Hint: Each direction must update its boundary after filling [OK]

Common Mistakes:

• Forgetting to update one boundary after a direction
• Incorrectly updating boundaries leading to index errors
• Misordering direction cycling

5. The following code attempts to return the spiral order of a matrix. Which line contains a subtle bug that can cause repeated elements or index errors?

medium

A. Line where bottom row is traversed without checking if top <= bottom

B. Line where right is decremented after traversing the right column

C. Line where left column is traversed with boundary check

D. Line where top is incremented after traversing the top row

Solution

1. Step 1: Identify missing boundary check

   The code traverses the bottom row without verifying if top <= bottom, which can cause duplicates or index errors when boundaries cross.

2. Step 2: Confirm other lines are correct

   Top increment, right decrement, and left column traversal have proper boundary checks or are logically correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing boundary check before bottom row traversal causes subtle bugs [OK]

Hint: Check boundary conditions before each traversal [OK]

Common Mistakes:

• Forgetting boundary checks before bottom or left traversal
• Incorrectly updating boundaries causing infinite loops
• Misplaced increments/decrements