Game of Life (Encode States In-Place)

🎯

Game of Life (Encode States In-Place)

mediumMATRIXAmazonFacebookGoogle

Imagine simulating the evolution of a cellular automaton on a grid, where each cell's next state depends on its neighbors, but you must do it without extra memory.

💡 This problem is about updating a matrix in-place based on neighbor states. Beginners often struggle because they try to update cells directly, which corrupts neighbor information needed for other cells. Encoding next states within current states helps solve this.

📋

Problem Statement

Given an m x n grid representing the current state of cells (1 for live, 0 for dead), compute the next state of the grid according to the following rules: 1) Any live cell with fewer than two live neighbors dies (underpopulation). 2) Any live cell with two or three live neighbors lives on. 3) Any live cell with more than three live neighbors dies (overpopulation). 4) Any dead cell with exactly three live neighbors becomes a live cell (reproduction). Update the board in-place to the next state.

m == board.lengthn == board[i].length1 ≤ m, n ≤ 100board[i][j] is 0 or 1

💡

Example

Input"[[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]]

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

• All cells dead → output remains all dead
• All cells live → some cells die due to overpopulation
• Single cell live → dies due to underpopulation
• Board with one row or one column → correctly handle edge neighbors

⚠️

Common Mistakes

Updating cells directly without preserving original states

Neighbor counts become incorrect, leading to wrong next states

✅ Use a copy or encode next state separately before final update

Not checking boundary conditions when counting neighbors

Index out of bounds errors or incorrect neighbor counts

✅ Always check indices are within valid range before accessing

Misinterpreting encoded states in in-place approaches

Incorrect neighbor counts or final states

✅ Clearly define and consistently use encoding scheme for old and new states

Forgetting to finalize the board after encoding next states

Board remains in encoded form, not updated to next state

✅ Add a final pass to decode and update all cells to their next states

🧠

Brute Force (Copy Board and Update)

💡 This approach uses extra memory to avoid corrupting neighbor information. It is straightforward and helps understand the problem deeply before optimizing.

Intuition

Create a copy of the board to read original states while updating the original board to the next state. This prevents interference between updates.

Algorithm

1. Create a deep copy of the original board.
2. For each cell, count live neighbors using the copy.
3. Apply the Game of Life rules to update the original board.
4. Return the updated board.

💡 The main challenge is to avoid reading updated cells when counting neighbors, which is solved by using a copy.

</>

Code

from copy import deepcopy

def gameOfLife(board):
    m, n = len(board), len(board[0])
    copy_board = deepcopy(board)
    directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    for i in range(m):
        for j in range(n):
            live_neighbors = 0
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and copy_board[x][y] == 1:
                    live_neighbors += 1
            if copy_board[i][j] == 1:
                if live_neighbors < 2 or live_neighbors > 3:
                    board[i][j] = 0
            else:
                if live_neighbors == 3:
                    board[i][j] = 1

# Example usage:
if __name__ == '__main__':
    board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
    gameOfLife(board)
    print(board)

Line Notes

from copy import deepcopyImport deepcopy to create a full copy of the board to avoid reference issues

copy_board = deepcopy(board)Create a snapshot of the original board to read original states safely

for i in range(m):Iterate over each row to process every cell

for dx, dy in directions:Check all eight neighbors around the current cell

if 0 <= x < m and 0 <= y < n and copy_board[x][y] == 1:Count only live neighbors within bounds

if copy_board[i][j] == 1:Apply rules for live cells based on neighbor count

board[i][j] = 0Update original board cell to dead if under/overpopulation

if live_neighbors == 3:Revive dead cell if exactly three live neighbors

import java.util.Arrays;

public class GameOfLife {
    public static void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        int[][] copyBoard = new int[m][n];
        for (int i = 0; i < m; i++)
            copyBoard[i] = Arrays.copyOf(board[i], n);
        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[] d : directions) {
                    int x = i + d[0], y = j + d[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && copyBoard[x][y] == 1) {
                        liveNeighbors++;
                    }
                }
                if (copyBoard[i][j] == 1) {
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        board[i][j] = 0;
                    }
                } else {
                    if (liveNeighbors == 3) {
                        board[i][j] = 1;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] board = {{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
        gameOfLife(board);
        for (int[] row : board) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

int[][] copyBoard = new int[m][n];Create a new 2D array to hold the original board state

copyBoard[i] = Arrays.copyOf(board[i], n);Copy each row to avoid referencing the original array

for (int[] d : directions)Iterate over all eight possible neighbor directions

if (x >= 0 && x < m && y >= 0 && y < n && copyBoard[x][y] == 1)Check bounds and count live neighbors safely

if (copyBoard[i][j] == 1)Apply rules for live cells based on neighbor count

board[i][j] = 0;Update original board cell to dead if conditions met

if (liveNeighbors == 3)Revive dead cell if exactly three live neighbors

#include <iostream>
#include <vector>
using namespace std;

void gameOfLife(vector<vector<int>>& board) {
    int m = board.size(), n = board[0].size();
    vector<vector<int>> copyBoard = board;
    vector<pair<int,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 (auto d : directions) {
                int x = i + d.first, y = j + d.second;
                if (x >= 0 && x < m && y >= 0 && y < n && copyBoard[x][y] == 1) {
                    liveNeighbors++;
                }
            }
            if (copyBoard[i][j] == 1) {
                if (liveNeighbors < 2 || liveNeighbors > 3) {
                    board[i][j] = 0;
                }
            } else {
                if (liveNeighbors == 3) {
                    board[i][j] = 1;
                }
            }
        }
    }
}

int main() {
    vector<vector<int>> board = {{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
    gameOfLife(board);
    for (auto& row : board) {
        for (int cell : row) cout << cell << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<vector<int>> copyBoard = board;Copy the board to preserve original states for neighbor checks

for (auto d : directions)Loop over all eight neighbor directions

if (x >= 0 && x < m && y >= 0 && y < n && copyBoard[x][y] == 1)Count live neighbors only if inside bounds

if (copyBoard[i][j] == 1)Apply rules for live cells based on neighbor count

board[i][j] = 0;Kill cell if underpopulation or overpopulation

if (liveNeighbors == 3)Revive dead cell if exactly three live neighbors

function gameOfLife(board) {
    const m = board.length, n = board[0].length;
    const copyBoard = board.map(row => row.slice());
    const directions = [[-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let liveNeighbors = 0;
            for (const [dx, dy] of directions) {
                const x = i + dx, y = j + dy;
                if (x >= 0 && x < m && y >= 0 && y < n && copyBoard[x][y] === 1) {
                    liveNeighbors++;
                }
            }
            if (copyBoard[i][j] === 1) {
                if (liveNeighbors < 2 || liveNeighbors > 3) {
                    board[i][j] = 0;
                }
            } else {
                if (liveNeighbors === 3) {
                    board[i][j] = 1;
                }
            }
        }
    }
}

// Example usage:
const board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]];
gameOfLife(board);
console.log(board);

Line Notes

const copyBoard = board.map(row => row.slice());Create a deep copy of the board to avoid modifying neighbor info prematurely

for (const [dx, dy] of directions)Iterate over all eight neighbors

if (x >= 0 && x < m && y >= 0 && y < n && copyBoard[x][y] === 1)Count live neighbors only if within bounds

if (copyBoard[i][j] === 1)Apply rules for live cells based on neighbor count

board[i][j] = 0;Kill cell if underpopulation or overpopulation

if (liveNeighbors === 3)Revive dead cell if exactly three live neighbors

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We visit each cell once and check up to 8 neighbors, so O(m*n). The copy requires O(m*n) space.

💡 For a 100x100 board, this means about 10,000 cells processed, which is efficient but uses extra memory.

Interview Verdict: Accepted

This approach works correctly but uses extra space, which can be improved.

🧠

In-Place Encoding Using Bit Manipulation

💡 This approach encodes the next state in the current board by using bits, allowing in-place updates without extra memory.

Intuition

Use the second bit of each cell to store the next state while preserving the current state in the first bit. After processing, shift bits to update.

Algorithm

1. For each cell, count live neighbors considering only the current state (lowest bit).
2. Determine the next state and store it in the second bit of the cell.
3. After processing all cells, update each cell by shifting bits to make the next state the current state.

💡 The tricky part is to read current states correctly while writing next states in the same cell.

</>

Code

def gameOfLife(board):
    m, n = len(board), len(board[0])
    directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    for i in range(m):
        for j in range(n):
            live_neighbors = 0
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and (board[x][y] & 1) == 1:
                    live_neighbors += 1
            if (board[i][j] & 1) == 1:
                if live_neighbors == 2 or live_neighbors == 3:
                    board[i][j] |= 2  # Set second bit to 1
            else:
                if live_neighbors == 3:
                    board[i][j] |= 2
    for i in range(m):
        for j in range(n):
            board[i][j] >>= 1

# Example usage:
if __name__ == '__main__':
    board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
    gameOfLife(board)
    print(board)

Line Notes

if 0 <= x < m and 0 <= y < n and (board[x][y] & 1) == 1:Check live neighbors using only the current state (lowest bit)

if (board[i][j] & 1) == 1:Check if current cell is live by inspecting lowest bit

board[i][j] |= 2Set second bit to 1 to encode next state as live

board[i][j] >>= 1Shift bits right to update cell to next state

public class GameOfLife {
    public static void gameOfLife(int[][] board) {
        int m = board.length, 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[] d : directions) {
                    int x = i + d[0], y = j + d[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] & 1) == 1) {
                        liveNeighbors++;
                    }
                }
                if ((board[i][j] & 1) == 1) {
                    if (liveNeighbors == 2 || liveNeighbors == 3) {
                        board[i][j] |= 2;
                    }
                } else {
                    if (liveNeighbors == 3) {
                        board[i][j] |= 2;
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] >>= 1;
            }
        }
    }

    public static void main(String[] args) {
        int[][] board = {{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
        gameOfLife(board);
        for (int[] row : board) {
            System.out.println(java.util.Arrays.toString(row));
        }
    }
}

Line Notes

if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] & 1) == 1)Count live neighbors by checking only the lowest bit

if ((board[i][j] & 1) == 1)Check current cell's live state using bitwise AND

board[i][j] |= 2;Set second bit to encode next state as live

board[i][j] >>= 1;Shift bits right to update to next state

#include <iostream>
#include <vector>
using namespace std;

void gameOfLife(vector<vector<int>>& board) {
    int m = board.size(), n = board[0].size();
    vector<pair<int,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 (auto d : directions) {
                int x = i + d.first, y = j + d.second;
                if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] & 1) == 1) {
                    liveNeighbors++;
                }
            }
            if ((board[i][j] & 1) == 1) {
                if (liveNeighbors == 2 || liveNeighbors == 3) {
                    board[i][j] |= 2;
                }
            } else {
                if (liveNeighbors == 3) {
                    board[i][j] |= 2;
                }
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] >>= 1;
        }
    }
}

int main() {
    vector<vector<int>> board = {{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
    gameOfLife(board);
    for (auto& row : board) {
        for (int cell : row) cout << cell << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] & 1) == 1)Count live neighbors by checking only the current state bit

if ((board[i][j] & 1) == 1)Check if current cell is live using bitwise AND

board[i][j] |= 2;Set second bit to encode next state as live

board[i][j] >>= 1;Shift bits right to update cell to next state

function gameOfLife(board) {
    const m = board.length, n = board[0].length;
    const directions = [[-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let liveNeighbors = 0;
            for (const [dx, dy] of directions) {
                const x = i + dx, y = j + dy;
                if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] & 1) === 1) {
                    liveNeighbors++;
                }
            }
            if ((board[i][j] & 1) === 1) {
                if (liveNeighbors === 2 || liveNeighbors === 3) {
                    board[i][j] |= 2;
                }
            } else {
                if (liveNeighbors === 3) {
                    board[i][j] |= 2;
                }
            }
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            board[i][j] >>= 1;
        }
    }
}

// Example usage:
const board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]];
gameOfLife(board);
console.log(board);

Line Notes

if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] & 1) === 1)Count live neighbors by checking only the current state bit

if ((board[i][j] & 1) === 1)Check if current cell is live using bitwise AND

board[i][j] |= 2;Set second bit to encode next state as live

board[i][j] >>= 1;Shift bits right to update cell to next state

⏱

Complexity

TimeO(m*n)

SpaceO(1)

We visit each cell once and check neighbors, but no extra space is used beyond input board.

💡 For a 100x100 board, this means about 10,000 cells processed with no extra memory, which is optimal.

Interview Verdict: Accepted

This is the optimal in-place solution that interviewers expect after the brute force approach.

🧠

In-Place Encoding Using State Mapping (4 States)

💡 This approach uses a 4-state encoding to represent transitions explicitly, which can be easier to understand than bit manipulation for some.

Intuition

Use integers 0,1,2,3 to represent dead->dead, live->live, live->dead, dead->live respectively, then decode after processing.

Algorithm

1. Traverse the board and count live neighbors using original states (0 or 1).
2. Update cells to 2 or 3 to encode transitions: 2 means live->dead, 3 means dead->live.
3. Traverse again to finalize states by converting 2 to 0 and 3 to 1.

💡 This approach separates transition states clearly, making debugging easier than bit tricks.

</>

Code

def gameOfLife(board):
    m, n = len(board), len(board[0])
    directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    for i in range(m):
        for j in range(n):
            live_neighbors = 0
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and board[x][y] in (1, 2):
                    live_neighbors += 1
            if board[i][j] == 1:
                if live_neighbors < 2 or live_neighbors > 3:
                    board[i][j] = 2  # live->dead
            else:
                if live_neighbors == 3:
                    board[i][j] = 3  # dead->live
    for i in range(m):
        for j in range(n):
            if board[i][j] == 2:
                board[i][j] = 0
            elif board[i][j] == 3:
                board[i][j] = 1

# Example usage:
if __name__ == '__main__':
    board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
    gameOfLife(board)
    print(board)

Line Notes

if 0 <= x < m and 0 <= y < n and board[x][y] in (1, 2):Count neighbors considering original live states and those marked live->dead (2) as live

board[i][j] = 2Mark live cell that will die as 2 to encode transition

board[i][j] = 3Mark dead cell that will become live as 3

if board[i][j] == 2:Convert transition state 2 back to dead (0)

elif board[i][j] == 3:Convert transition state 3 back to live (1)

public class GameOfLife {
    public static void gameOfLife(int[][] board) {
        int m = board.length, 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[] d : directions) {
                    int x = i + d[0], y = j + d[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] == 1 || board[x][y] == 2)) {
                        liveNeighbors++;
                    }
                }
                if (board[i][j] == 1) {
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        board[i][j] = 2;
                    }
                } else {
                    if (liveNeighbors == 3) {
                        board[i][j] = 3;
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 2) {
                    board[i][j] = 0;
                } else if (board[i][j] == 3) {
                    board[i][j] = 1;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] board = {{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
        gameOfLife(board);
        for (int[] row : board) {
            System.out.println(java.util.Arrays.toString(row));
        }
    }
}

Line Notes

if (board[x][y] == 1 || board[x][y] == 2)Count neighbors considering original live and live->dead states as live

board[i][j] = 2;Mark live cell that will die as 2

board[i][j] = 3;Mark dead cell that will become live as 3

if (board[i][j] == 2)Convert 2 back to dead (0)

else if (board[i][j] == 3)Convert 3 back to live (1)

#include <iostream>
#include <vector>
using namespace std;

void gameOfLife(vector<vector<int>>& board) {
    int m = board.size(), n = board[0].size();
    vector<pair<int,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 (auto d : directions) {
                int x = i + d.first, y = j + d.second;
                if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] == 1 || board[x][y] == 2)) {
                    liveNeighbors++;
                }
            }
            if (board[i][j] == 1) {
                if (liveNeighbors < 2 || liveNeighbors > 3) {
                    board[i][j] = 2;
                }
            } else {
                if (liveNeighbors == 3) {
                    board[i][j] = 3;
                }
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 2) board[i][j] = 0;
            else if (board[i][j] == 3) board[i][j] = 1;
        }
    }
}

int main() {
    vector<vector<int>> board = {{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
    gameOfLife(board);
    for (auto& row : board) {
        for (int cell : row) cout << cell << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

if (board[x][y] == 1 || board[x][y] == 2)Count neighbors considering original live and live->dead states

board[i][j] = 2;Mark live cell that will die as 2

board[i][j] = 3;Mark dead cell that will become live as 3

if (board[i][j] == 2) board[i][j] = 0;Convert 2 back to dead

else if (board[i][j] == 3) board[i][j] = 1;Convert 3 back to live

function gameOfLife(board) {
    const m = board.length, n = board[0].length;
    const directions = [[-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let liveNeighbors = 0;
            for (const [dx, dy] of directions) {
                const x = i + dx, y = j + dy;
                if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] === 1 || board[x][y] === 2)) {
                    liveNeighbors++;
                }
            }
            if (board[i][j] === 1) {
                if (liveNeighbors < 2 || liveNeighbors > 3) {
                    board[i][j] = 2;
                }
            } else {
                if (liveNeighbors === 3) {
                    board[i][j] = 3;
                }
            }
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 2) board[i][j] = 0;
            else if (board[i][j] === 3) board[i][j] = 1;
        }
    }
}

// Example usage:
const board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]];
gameOfLife(board);
console.log(board);

Line Notes

if (board[x][y] === 1 || board[x][y] === 2)Count neighbors considering original live and live->dead states

board[i][j] = 2;Mark live cell that will die as 2

board[i][j] = 3;Mark dead cell that will become live as 3

if (board[i][j] === 2) board[i][j] = 0;Convert 2 back to dead

else if (board[i][j] === 3) board[i][j] = 1;Convert 3 back to live

⏱

Complexity

TimeO(m*n)

SpaceO(1)

We scan the board twice but use no extra space beyond input.

💡 This approach is easy to understand and uses constant space, suitable for interviews.

Interview Verdict: Accepted

This is a clean in-place solution that balances clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, start with brute force to show understanding, then code the in-place encoding approach for optimal space.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Copy Board)	O(m*n)	O(m*n)	No	N/A	Mention only - never code unless asked for clarity
2. In-Place Encoding Using Bit Manipulation	O(m*n)	O(1)	No	N/A	Code this for optimal space and performance
3. In-Place Encoding Using State Mapping (4 States)	O(m*n)	O(1)	No	N/A	Good alternative if bit manipulation is unclear

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly.

How to Present

Clarify input/output and rules with the interviewer.Explain brute force approach using a copy of the board.Discuss its space inefficiency and motivate in-place encoding.Present bit manipulation or state mapping approaches.Write clean code and test with examples.

Time Allocation

Clarify: 3min → Brute Force: 7min → In-Place Encoding: 10min → Testing & Edge Cases: 5min. Total ~25min

What the Interviewer Tests

Understanding of in-place updates, bit manipulation or encoding techniques, boundary conditions, and ability to optimize space.

Common Follow-ups

• How to handle infinite board or streaming updates → Use hash sets or sparse representations.
• Can you optimize neighbor counting? → Use memoization or precompute neighbor counts.

💡 These follow-ups test your ability to extend the solution beyond the basic problem and optimize further.

🔍

Pattern Recognition

When to Use

1) You need to update a matrix based on neighbors; 2) The update must be in-place; 3) Next state depends on current states only; 4) Encoding states is possible.

Signature Phrases

update board in-placenext state depends on neighborsencode next state in current state

NOT This Pattern When

Problems that require separate DP tables or do not update in-place are different patterns.

Similar Problems

Surrounded Regions - also requires in-place marking and decodingNumber of Islands - neighbor traversal in gridsRotting Oranges - BFS with state updates in grid

Practice

1. You are given a 2D matrix and need to output its elements in a zigzag pattern that moves along the diagonals, alternating direction each diagonal. Which algorithmic approach best guarantees an optimal solution for this traversal?

easy

A. Simulate diagonal traversal by iterating over each diagonal and alternating direction for each diagonal.

B. Use a greedy approach that picks the next element based on local maximum value.

C. Apply dynamic programming to store intermediate sums along diagonals.

D. Perform a breadth-first search (BFS) starting from the top-left corner.

Solution

1. Step 1: Understand the traversal pattern

   The problem requires visiting elements along diagonals, alternating direction each diagonal, which matches a diagonal traversal pattern.

2. Step 2: Identify the approach that matches this pattern

   Simulating traversal by iterating over each diagonal and alternating direction ensures all elements are visited in the required order efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal iteration with direction flip matches problem requirements [OK]

Hint: Diagonal traversal alternates direction per diagonal [OK]

Common Mistakes:

• Confusing with BFS or DP which don't fit traversal order

2. What is the time complexity of the optimal approach to compute the sum of the diagonals of an n x n matrix using a single loop that sums mat[i][i] and mat[i][n-1-i] for i in [0, n-1]?

medium

A. O(n) because the loop runs n times and each iteration does constant work

B. O(n^2) because we access two elements per iteration and n iterations

C. O(1) because only two elements are accessed per iteration

D. O(n log n) due to index calculations inside the loop

Solution

1. Step 1: Identify loop iterations

   The loop runs exactly n times, once for each row index i.

2. Step 2: Analyze work per iteration

   Each iteration accesses exactly two elements and performs constant time addition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time O(n) matches single loop with constant work [OK]

Hint: Single loop with constant work per iteration is O(n) [OK]

Common Mistakes:

• Confusing element accesses with nested loops
• Assuming index calculations add log n factor
• Mistaking constant work for O(1) total

3. Suppose the matrix is no longer sorted row-wise or column-wise but only each row is sorted independently. Which approach correctly counts negative numbers efficiently in this scenario?

hard

A. Use the staircase search from top-right corner as before.

B. Use brute force nested loops to check every element.

C. Perform binary search on each row to find the first negative number and sum counts.

D. Apply dynamic programming to store counts of negatives in submatrices.

Solution

1. Step 1: Analyze sorting constraints

   Only rows are sorted, columns are not, so staircase search relying on column sorting fails.

2. Step 2: Choose correct approach

   Binary search per row finds first negative efficiently in O(log n), total O(m log n), better than brute force.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Row-wise binary search exploits partial sorting [OK]

Hint: When only rows sorted, binary search per row is optimal [OK]

Common Mistakes:

• Trying staircase search without column sorting
• Using brute force ignoring partial sorting
• Assuming DP is needed

4. Suppose the matrix can contain duplicate values and you want to find all lucky numbers (minimum in their row and maximum in their column). Which modification to the optimal approach correctly handles duplicates without missing any lucky numbers?

hard

A. After precomputing row minimums and column maximums, return only the first element matching both conditions per row to avoid duplicates.

B. Use sets to store all minimum values per row and maximum values per column, then find all elements that appear in both sets.

C. Modify the single pass to check if the element equals the row minimum and column maximum, allowing multiple lucky numbers per row or column.

D. Sort each row and column and pick the intersection of minimums and maximums to find lucky numbers.

Solution

1. Step 1: Understand duplicates impact

   Duplicates mean multiple elements in a row can be minimum and multiple in a column can be maximum.

2. Step 2: Modify single pass check

   Instead of returning only one per row, check each element if it equals the row minimum and column maximum, allowing multiple lucky numbers.

3. Step 3: Avoid unnecessary data structures

   Using sets (B) or sorting (D) adds overhead and complexity without benefit. Returning only first match (A) misses valid lucky numbers.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Check all elements against precomputed mins and maxs -> handles duplicates [OK]

Hint: Check all elements, not just first per row [OK]

Common Mistakes:

• Returning only first match per row
• Using extra data structures unnecessarily
• Sorting instead of direct checks

5. Suppose the problem changes: you want to find the top 3 maximum hourglass sums in the matrix instead of just the maximum. Which modification to the sliding window approach is correct and efficient?

hard

A. Store all hourglass sums in a list and sort it at the end to pick top 3.

B. Run the sliding window 3 times, each time removing the previously found max hourglass from the matrix.

C. Maintain a min-heap of size 3 to track top sums while sliding through the matrix.

D. Use dynamic programming to store maximum sums for all submatrices and pick top 3.

Solution

1. Step 1: Understand the need to track multiple top sums efficiently

   Storing all sums and sorting is inefficient for large matrices.

2. Step 2: Use a min-heap of fixed size 3

   Insert sums as you compute; if heap size exceeds 3, pop smallest. This keeps top 3 sums efficiently.

3. Step 3: Reject other options

   Sorting all sums (A) is costly; repeated removal (C) is complex and incorrect; DP (D) is unnecessary and inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Min-heap maintains top K sums in O(n*m*logK) time [OK]

Hint: Use min-heap to track top K sums efficiently [OK]

Common Mistakes:

• Sorting all sums after computation
• Repeatedly removing max sums from matrix
• Using DP unnecessarily