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

1. Simulation problems reward faithful modeling over cleverness — read the rules and follow them exactly.
2. Choose your state deliberately: counters, sets, or a single rolling row, matched to what the question asks.
3. Incremental counters turn repeated full-board scans into O(1) checks per step.
4. Sets make uniqueness constraints trivial — a failed insert is a duplicate.
5. Bound enumeration with the square root and divisor pairing to keep brute force fast.