Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Matrix Simulation
DSA

Matrix Simulation

Learn how to carefully model and execute step-by-step operations in matrix simulation problems.

Matrix Simulation processes each cell according to rules, usually based on its neighbors.

Focus on recognizing:

“Next state of the grid” / “update all cells simultaneously” → neighbor rules + (often) state encoding

Pattern 1: Neighbor Counting

Watch Game of Life rules decide one step of a 3×3 board — a survivor with 3 neighbors and a reproduction at the corner. Press ▶ to animate.

Conway's Game of Life

Simulate one generation of Conway's Game of Life. A live cell with 2–3 live neighbors survives; a dead cell with exactly 3 live neighbors becomes alive; all others die or stay dead. The next state is computed from a copy of the current grid.

Grid: 1 = alive, 0 = dead. Count each cell's 8 live neighbors against the current grid, then apply the rules. The final step reveals the next generation. Watch the live center survive (3 neighbors) and the dead corner (0,0) become born (3 neighbors).

GRID VISUALIZER
Steps –
0
1
0
1
1
0
0
0
0
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        for each cell: count live neighbors (8 directions)
                      
                        2
                        live cell + 2 or 3 neighbors → stays alive
                      
                        3
                        dead cell + exactly 3 neighbors → becomes alive
                      
                        4
                        else → dead next round   (compute from a COPY)

The universal building block — 8-direction deltas:

private static final int[][] DIRS = {
    {-1, -1}, {-1, 0}, {-1, 1},
    { 0, -1},          { 0, 1},
    { 1, -1}, { 1, 0}, { 1, 1}
};

public int countLiveNeighbors(int[][] grid, int r, int c) {
    int rows = grid.length, cols = grid[0].length;
    int live = 0;

    for (int[] dir : DIRS) {
        int nr = r + dir[0];
        int nc = c + dir[1];

        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                && grid[nr][nc] == 1) {
            live++;
        }
    }

    return live;
}
DIRS = [(-1, -1), (-1, 0), (-1, 1),
        (0, -1),           (0, 1),
        (1, -1), (1, 0), (1, 1)]

def count_live_neighbors(grid, r, c):
    rows, cols = len(grid), len(grid[0])

    return sum(
        1
        for dr, dc in DIRS
        if 0 <= r + dr < rows and 0 <= c + dc < cols
        and grid[r + dr][c + dc] == 1
    )
static const int DIRS[8][2] = {
    {-1, -1}, {-1, 0}, {-1, 1},
    { 0, -1},          { 0, 1},
    { 1, -1}, { 1, 0}, { 1, 1}
};

int countLiveNeighbors(vector<vector<int>>& grid, int r, int c) {
    int rows = grid.size(), cols = grid[0].size();
    int live = 0;

    for (auto& dir : DIRS) {
        int nr = r + dir[0], nc = c + dir[1];

        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                && grid[nr][nc] == 1)
            live++;
    }

    return live;
}
const DIRS = [
  [-1, -1],
  [-1, 0],
  [-1, 1],
  [0, -1],
  [0, 1],
  [1, -1],
  [1, 0],
  [1, 1],
];

function countLiveNeighbors(grid, r, c) {
  const rows = grid.length,
    cols = grid[0].length;
  let live = 0;

  for (const [dr, dc] of DIRS) {
    const nr = r + dr,
      nc = c + dc;

    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1)
      live++;
  }

  return live;
}

Bounds check first, then the condition — every grid simulation starts here.

Pattern 2: Game of Life (In-Place State Encoding)

The catch: cells update simultaneously, but later cells still need the OLD values. Trick — encode transitions in place:

2 = was alive → dies     3 = was dead → becomes alive

Values 1 and 2 both mean “was alive” when counting neighbors:

public void gameOfLife(int[][] board) {
    int rows = board.length, cols = board[0].length;

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {

            int live = countLive(board, r, c);

            if (board[r][c] == 1 && (live < 2 || live > 3))
                board[r][c] = 2;         // alive → dead
            else if (board[r][c] == 0 && live == 3)
                board[r][c] = 3;         // dead → alive
        }
    }

    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (board[r][c] == 2) board[r][c] = 0;
            else if (board[r][c] == 3) board[r][c] = 1;
}

private int countLive(int[][] board, int r, int c) {
    int rows = board.length, cols = board[0].length, live = 0;

    for (int dr = -1; dr <= 1; dr++) {
        for (int dc = -1; dc <= 1; dc++) {
            if (dr == 0 && dc == 0) continue;

            int nr = r + dr, nc = c + dc;

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && (board[nr][nc] == 1 || board[nr][nc] == 2)) {
                live++;                  // 1 or 2 = was alive
            }
        }
    }

    return live;
}
def game_of_life(board):
    rows, cols = len(board), len(board[0])

    def count_live(r, c):
        total = 0

        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if dr == dc == 0:
                    continue

                nr, nc = r + dr, c + dc

                if 0 <= nr < rows and 0 <= nc < cols \
                        and board[nr][nc] in (1, 2):   # was alive
                    total += 1

        return total

    for r in range(rows):
        for c in range(cols):
            live = count_live(r, c)

            if board[r][c] == 1 and live not in (2, 3):
                board[r][c] = 2       # alive → dead
            elif board[r][c] == 0 and live == 3:
                board[r][c] = 3       # dead → alive

    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 2:
                board[r][c] = 0
            elif board[r][c] == 3:
                board[r][c] = 1
int countLive(vector<vector<int>>& board, int r, int c) {
    int rows = board.size(), cols = board[0].size(), live = 0;

    for (int dr = -1; dr <= 1; dr++) {
        for (int dc = -1; dc <= 1; dc++) {
            if (dr == 0 && dc == 0) continue;

            int nr = r + dr, nc = c + dc;

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && (board[nr][nc] == 1 || board[nr][nc] == 2))
                live++;              // 1 or 2 = was alive
        }
    }

    return live;
}

void gameOfLife(vector<vector<int>>& board) {
    int rows = board.size(), cols = board[0].size();

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {

            int live = countLive(board, r, c);

            if (board[r][c] == 1 && (live < 2 || live > 3))
                board[r][c] = 2;     // alive → dead
            else if (board[r][c] == 0 && live == 3)
                board[r][c] = 3;     // dead → alive
        }
    }

    for (auto& row : board)
        for (auto& cell : row) {
            if (cell == 2) cell = 0;
            else if (cell == 3) cell = 1;
        }
}
function gameOfLife(board) {
  const rows = board.length,
    cols = board[0].length;

  const countLive = (r, c) => {
    let live = 0;

    for (let dr = -1; dr <= 1; dr++) {
      for (let dc = -1; dc <= 1; dc++) {
        if (dr === 0 && dc === 0) continue;

        const nr = r + dr,
          nc = c + dc;

        if (
          nr >= 0 &&
          nr < rows &&
          nc >= 0 &&
          nc < cols &&
          (board[nr][nc] === 1 || board[nr][nc] === 2)
        )
          live++; // 1 or 2 = was alive
      }
    }

    return live;
  };

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const live = countLive(r, c);

      if (board[r][c] === 1 && (live < 2 || live > 3)) board[r][c] = 2;
      else if (board[r][c] === 0 && live === 3) board[r][c] = 3;
    }
  }

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === 2) board[r][c] = 0;
      else if (board[r][c] === 3) board[r][c] = 1;
    }
}

Simultaneous updates + in-place requirement → encode old→new in spare bits, decode on a second pass.

Pattern 3: Sudoku Validation

No neighbors here — track what has already appeared per row, column and 3×3 box:

public boolean isValidSudoku(char[][] board) {
    Set<String> seen = new HashSet<>();

    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char val = board[r][c];

            if (val == '.') continue;

            String rowKey = "row" + r + val;
            String colKey = "col" + c + val;
            String boxKey = "box" + (r / 3) + (c / 3) + val;

            if (!seen.add(rowKey) || !seen.add(colKey)
                    || !seen.add(boxKey)) {
                return false;
            }
        }
    }

    return true;
}
def is_valid_sudoku(board):
    seen = set()

    for r in range(9):
        for c in range(9):
            val = board[r][c]

            if val == ".":
                continue

            keys = (
                ("row", r, val),
                ("col", c, val),
                ("box", r // 3, c // 3, val),
            )

            for key in keys:
                if key in seen:
                    return False
                seen.add(key)

    return True
bool isValidSudoku(vector<vector<char>>& board) {
    unordered_set<string> seen;

    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char val = board[r][c];

            if (val == '.') continue;

            string keys[3] = {
                "row" + to_string(r) + val,
                "col" + to_string(c) + val,
                "box" + to_string(r / 3) + to_string(c / 3) + val
            };

            for (auto& key : keys) {
                if (!seen.insert(key).second) return false;
            }
        }
    }

    return true;
}
function isValidSudoku(board) {
  const seen = new Set();

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const val = board[r][c];

      if (val === ".") continue;

      for (const key of [
        `row${r}${val}`,
        `col${c}${val}`,
        `box${(r / 3) | 0}${((c / 3) | 0)}${val}`,
      ]) {
        if (seen.has(key)) return false;
        seen.add(key);
      }
    }
  }

  return true;
}

Box index (r/3, c/3) maps each cell to its 3×3 quadrant — the whole trick.

Common Mistakes

Overwriting cells during simultaneous updates.

Game of Life breaks unless you encode transitions (or copy the board).

Forgetting bounds checks.

Every neighbor access needs 0 <= nr < rows && 0 <= nc < cols.

Wrong box index in Sudoku.

(r / 3, c / 3) — not (r % 3, c % 3).

Complexity

PatternTimeSpace
Neighbor countO(n·m·8)O(1)
Game of LifeO(n·m)O(1) in-place
Sudoku validateO(81)O(81)

My Private Notes

Notes are auto-saved locally to this device.