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.
Valid Sudoku
Core idea: A Sudoku board is valid when three independent uniqueness rules all hold: no digit repeats within a row, within a column, or within a 3×3 box. Each filled cell
board[r][c]belongs to exactly one row (r), one column (c), and one box ((r//3, c//3)). So you don't need to solve anything — you just walk every cell once and drop its digit into three "seen" sets keyed by those three group identities. The first time a digit is already in any of its three sets, the board is invalid. The whole trick is the box key(r // 3, c // 3), which maps a cell to its 3×3 block.
Problem, rephrased
You're handed a 9×9 grid, partly filled in. Each cell holds either a digit '1'–'9' or a dot '.' meaning empty. You are not asked whether the puzzle is solvable or to fill it in — only whether the digits already placed break any rule.
A board is valid when all three of these hold:
- Each row contains each digit
1–9at most once. - Each column contains each digit
1–9at most once. - Each of the nine 3×3 boxes contains each digit
1–9at most once.
Empty cells ('.') impose no constraint — skip them. Return True if every rule holds, False otherwise.
| Input (sketch) | Output | Why |
|---|---|---|
| A standard puzzle with no repeats | True |
every row, column, and box has distinct digits |
Two 5s in the same row |
False |
row uniqueness violated |
Two 8s in the same 3×3 box (different rows/cols) |
False |
box uniqueness violated even though row & col are fine |
Completely empty board ('.' everywhere) |
True |
no digits placed → no rule can be broken |
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