Grid and Simulation
What is this?
These are problems with no clever algorithm to find — you just walk through a grid or follow a set of rules step by step, exactly as written. The skill is bookkeeping: keep the right counters and sets, update them as you go, and never let your simulation drift away from what the rules actually say. Get the details right and the answer falls out on its own.
💡 Fun fact: Tic-Tac-Toe has only 765 truly distinct board positions once you remove rotations and reflections — small enough that a perfect player can be hardcoded, which is exactly why the interview version asks you to design O(1) win checks instead of brute-forcing the board.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: some problems do not reward a clever trick — they reward faithfully modeling the rules and walking the data exactly as described. The skill is bookkeeping: pick the right counters and sets, update them as you scan, and never let the simulation drift from the spec.
The pattern
Every problem here is solved by reading the rules literally and tracking just enough state to answer the question in one pass. The win comes from choosing what to store, not from a fancier algorithm.
- Build row from previous row. When each line depends only on the one above it, keep a single array and derive the next from it, rather than recomputing everything from scratch each time.
- Incremental counters instead of full scans. Maintain per-row, per-column, and per-diagonal tallies that you bump on each move, so you can detect a winning or invalid state in O(1) instead of re-scanning the whole board.
- Sets for "seen already." A grid with uniqueness constraints (rows, columns, sub-boxes) is just three families of sets; a value that fails to insert is a duplicate.
- Bound the work with math. When you must enumerate divisors or factors, walk only up to the square root and pair each divisor with its complement, turning O(n) into O(sqrt n).
The common thread: define your state up front, decide how each step mutates it, and trust the loop.
The problems
Pascal's Triangle — build each row from the previous one, since every interior entry is the sum of the two values above it. Keep only the last row and extend it; no full grid needed.
Design Tic-Tac-Toe — instead of scanning the board after every move, keep per-row and per-column counters plus two diagonal counters. A player who pushes any counter to the board size has just won, checked in O(1) per move.
Valid Sudoku — track a set for each row, each column, and each 3x3 box. Scan the board once; the moment a digit fails to insert into its row, column, or box set, the board is invalid.
Perfect Number — sum the proper divisors by iterating only up to the square root, adding both i and n / i for each divisor pair, then comparing the total to the number itself.
Key takeaways
- Simulation problems reward faithful modeling over cleverness — read the rules and follow them exactly.
- Choose your state deliberately: counters, sets, or a single rolling row, matched to what the question asks.
- Incremental counters turn repeated full-board scans into O(1) checks per step.
- Sets make uniqueness constraints trivial — a failed insert is a duplicate.
- Bound enumeration with the square root and divisor pairing to keep brute force fast.
Design Tic-Tac-Toe
Core idea: A move can only ever complete the row it lands in, the column it lands in, or (if it's on a diagonal) one of the two diagonals. So instead of scanning the board after every move, keep a running tally per row, per column, and for the two diagonals. Encode player 1 as
+1and player 2 as-1; the instant any tally a move touches hits+nor-n, that player has filled a line — a win, detected in O(1) without ever looking at the board.
1. The problem, in a fresh setting
You're building the game server for a real-time n × n tic-tac-toe app. Two players alternate dropping their marks; the server must answer one question after every move, instantly: did that move just win the game?
Implement a TicTacToe class:
| Operation | Meaning |
|---|---|
TicTacToe(n) |
construct the game on an empty n × n board |
move(row, col, player) -> int |
player (1 or 2) places a mark at (row, col); return the winning player if this move wins, else 0 |
Rules to bank: each cell is played at most once, moves are valid, and a player wins by filling any full row, any full column, or either main diagonal with their own mark. The classic win condition — return the winner the moment it happens.
Example trace on a 3 × 3 board (player 1 = X, player 2 = O):
| Call | Returns | Why |
|---|---|---|
move(0, 0, 1) |
0 | X at top-left; no line full yet |
move(0, 2, 2) |
0 | O at top-right |
move(2, 2, 1) |
0 | X at bottom-right |
move(1, 1, 2) |
0 | O at center |
move(2, 0, 1) |
0 | X at bottom-left |
move(1, 0, 2) |
0 | O at middle-left |
move(2, 1, 1) |
1 | X completes the bottom row → player 1 wins |
That last row is the whole game: after placing the third X in row 2, the answer flips from 0 to 1 — and we want to know that without re-reading nine cells.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson