Simulation and Stateful Iteration

Some problems have no trick. The statement describes a process, and the task is to execute it exactly, without an off-by-one or a missed case. Interviewers use these deliberately: they measure whether you can hold several pieces of state straight and translate a specification faithfully — which is most of real engineering.

There are still techniques, and they are worth having ready:

• Direction vectors instead of four hard-coded branches.
• In-place state encoding when reads and writes collide.
• Recognising when not to simulate — the most valuable one, because some problems describe a billion steps and expect you to reason instead.

What you’ll learn

• Rotating a direction in one line, with no if chain.
• The two-bit trick for simultaneous updates in $O(1)$ space.
• Bouncing state machines — the step variable that replaces modular index arithmetic.
• The cycle argument: why four iterations settle a rotation question forever.
• Three real LeetCode problems solved in the browser: 289, 1041, 6.

The cue

You are looking at a simulation when…

• The statement describes rules applied repeatedly — 289, 874, 1041.
• A robot, cursor or pointer moves and turns — 1041, 874, 657.
• Output must be built in an unusual traversal order — 6 zigzag, 54 spiral, 68 justification.
• The problem is mostly formatting or parsing — 68, 12, 273.
• There is no obvious data structure, and the statement is unusually long. That length is the signal.

The anti-cue — important: if the number of steps is enormous ($10^9$ moves, $10^{18}$ iterations), you are not meant to simulate. Look for a cycle, a closed form, or an invariant.

Visual intuition

A simulation is a state machine over a grid, advanced one tick at a time. Rotting Oranges is the cleanest instance in the library: every cell’s next state depends on its neighbours’ current state, and each frame here is one complete tick.

gridOne tick at a time: every cell reads its neighbours' current stateLC 994 · the shape of every grid simulation

×🍊🍊🍊🍊🍊🍊

rotten front

0,0

minute0fresh left6

1def oranges_rotting(grid):2    q = deque()3    fresh = 04    for r, row in enumerate(grid):5        for c, v in enumerate(row):6            if v == 2: q.append((r, c))     # EVERY rotten one seeds the queue7            elif v == 1: fresh += 18    minutes = 09    while q and fresh:10        for _ in range(len(q)):             # one whole minute per level11            r, c = q.popleft()12            for dr, dc in DIRS:13                if grid[nr][nc] == 1:14                    grid[nr][nc] = 2; fresh -= 1; q.append((nr, nc))15        minutes += 116    return -1 if fresh else minutes

sources1fresh6

setup1 orange is already rotten, and **all of them** seed the queue at once. That is the multi-source trick: several starting points in one BFS, which spreads from all of them simultaneously rather than needing one search per source.

Play‹›1/6⟲

Watch the frame boundaries rather than the individual cells. Everything that changes within one tick was decided by the state at the START of that tick -- which is exactly the read-then-write discipline this page is about. Update in place with no separation and a cell rotted this tick would start rotting its own neighbours in the same tick.

Trick 1 — direction vectors

Four if branches for up/down/left/right is where bugs live. A vector list plus an index is shorter and rotates in one line:

direction_vectors.py

# clockwise order: north, east, south, west
DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))
 
facing = 0                       # index into DIRS
facing = (facing + 1) % 4        # turn RIGHT
facing = (facing - 1) % 4        # turn LEFT  (Python's % keeps it non-negative)
 
dx, dy = DIRS[facing]
x, y = x + dx, y + dy            # step forward

Keeping the directions in clockwise order is what makes +1 a right turn. Python’s modulo returning a non-negative result for a positive divisor means (0 - 1) % 4 == 3 — so turning left from index 0 correctly gives west, with no special case. In C or Java that expression yields -1 and needs + 4 first.

An equally clean alternative avoids the index entirely:

rotate_in_place.py

dx, dy = -dy, dx      # rotate LEFT  90 degrees
dx, dy = dy, -dx      # rotate RIGHT 90 degrees

Worth memorising — it is two characters of difference, and getting the pair backwards mirrors the whole simulation.

Trick 2 — encode two states in one cell

Game of Life updates every cell based on its neighbours’ current values. Write as you read and you corrupt the input mid-pass.

The $O(1)$-space fix stores both states in the same integer: bit 0 is the present, bit 1 is the future.

game_of_life_bits.py

def game_of_life(board):
    rows, cols = len(board), len(board[0])
 
    for r in range(rows):
        for c in range(cols):
            live = 0
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    if dr == 0 and dc == 0:
                        continue
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols:
                        live += board[nr][nc] & 1        # read ONLY bit 0
            # write the next state into bit 1
            if board[r][c] & 1:
                if live in (2, 3):
                    board[r][c] |= 2
            elif live == 3:
                board[r][c] |= 2
 
    for r in range(rows):                                # second pass: shift
        for c in range(cols):
            board[r][c] >>= 1
    return board

Why & 1 and |= 2 keep the passes independent

board[nr][nc] & 1 reads only the original value, so a neighbour already updated this pass still reports its old state. |= 2 writes the new state into a bit nobody reads. The two passes therefore cannot interfere.

A second pass then shifts every cell right by one, promoting the future into the present.

The simpler alternative — copy the board and read from the copy — is $O(mn)$ space and completely acceptable. Say it first, then offer the bit encoding when asked for $O(1)$. The point of the trick is not that copying is bad; it is that “encode the new state where the old reader cannot see it” is a reusable idea.

Trick 3 — bouncing state

For zigzag traversal (LC 6), the row index goes down then up then down. Modular arithmetic on the cycle length works but is fiddly; a step variable that flips at the boundaries is much clearer:

zigzag.py

def convert(s, num_rows):
    if num_rows == 1:
        return s                      # no zigzag exists; also avoids a hang
    rows = [[] for _ in range(num_rows)]
    row, step = 0, 1
 
    for ch in s:
        rows[row].append(ch)
        if row == 0:
            step = 1                  # bounce off the top
        elif row == num_rows - 1:
            step = -1                 # bounce off the bottom
        row += step
 
    return "".join("".join(r) for r in rows)

num_rows == 1 must be handled explicitly

With one row, row is both 0 and num_rows - 1. The first branch sets step = 1, so row becomes 1 — out of range — and the next append raises IndexError.

Guarding num_rows == 1 up front returns the string unchanged, which is also the correct answer. Note the checks are ordered if row == 0 before elif row == num_rows - 1 precisely so that the ambiguous single-row case is resolved — and the guard is what makes that safe rather than merely lucky.

Trick 4 — do not simulate

This is the most valuable habit on the page.

LC 1041 asks whether a robot stays within a bounded circle when its instruction string repeats forever. Simulating forever is impossible. The insight:

After four repetitions, the robot’s net rotation is a multiple of 360°, so its displacement pattern repeats. So it is bounded if and only if, after one pass, either it is back at the origin or it is no longer facing its original direction.

If the robot ends facing north again (unrotated) at a non-origin position, each repetition adds the same displacement and it escapes. If it has rotated at all, four passes compose into a closed loop and it is bounded.

robot_bounded.py

def is_robot_bounded(instructions):
    x = y = 0
    dx, dy = 0, 1                     # facing north
    for ch in instructions:
        if ch == "G":
            x, y = x + dx, y + dy
        elif ch == "L":
            dx, dy = -dy, dx
        else:                         # "R"
            dx, dy = dy, -dx
    return (x == 0 and y == 0) or (dx, dy) != (0, 1)

One pass, $O(n)$, no loop over repetitions at all.

Problem	Naive	Better
289 Game of Life	$O(mn)$ space copy	$O(1)$ space via bit encoding
1041 Robot Bounded	simulate forever	one pass + a rotation argument
6 Zigzag	build the full grid, $O(n \cdot \text{rows})$	bucket per row, $O(n)$

Dry run

Game of Life (LC 289) with the two-bit trick, on

text

0 1 0
0 0 1
1 1 1
0 0 0

Pass 1 reads bit 0 only and writes the next state into bit 1. A few representative cells:

cell	current (bit 0)	live neighbours	rule	writes bit 1?
(0,1)	1	1 — only (1,2)	live with <2 → dies	no
(1,0)	0	3 — (0,1), (2,0), (2,1)	dead with exactly 3 → born	yes
(2,1)	1	3	live with 2 or 3 → survives	yes
(1,1)	0	5	dead, not exactly 3 → stays dead	no

Pass 2 shifts every cell right by one, promoting bit 1 to bit 0:

text

0 0 0
1 0 1
0 1 1
0 1 0

• The two passes are not an optimisation, they are the correctness argument. Every cell must read its neighbours’ current generation. Writing the answer into bit 1 leaves bit 0 untouched, so a cell processed later still sees the original values — that is what board[nr][nc] & 1 is protecting.
• A cell already carrying a future bit reads back correctly anyway. After (1,0) is set to binary 10, a later neighbour reading it computes 0b10 & 1 = 0 — its current state, which is right. The encoding survives being read mid-pass, which is why one array suffices.
• The alternative — copying the board — is $O(mn)$ space and completely correct. Say it first. The bit trick is the answer to “now do it in place”, and the interviewer is asking precisely because in-place updates of a neighbour-dependent rule are where people write the bug.
• The infinite-board follow-up changes the representation, not the rule: store only the live cells in a set, count neighbours from a Counter over their neighbourhoods, and the grid’s dimensions disappear from the problem.

Robot Bounded In Circle (LC 1041) — the “do not simulate” case. Simulating forever is not an option, and the insight is that four cycles always return to the starting orientation. So run the instruction string once: if the final facing is not north, the path must close within four cycles; if it is north, the robot is bounded only when the net displacement is (0, 0). One pass over the string, $O(n)$, no loop over time at all.

Complexity

Problem	Time	Space
LC 54 / 59 Spiral matrix	$O(mn)$	$O(1)$ beyond the output
LC 48 Rotate image in place	$O(n^2)$	$O(1)$ — transpose then reverse each row
LC 289 Game of Life, copied board	$O(mn)$	$O(mn)$
LC 289, two-bit encoding	$O(mn)$	$O(1)$
LC 289, infinite board	$O(k)$ in the live-cell count	$O(k)$
LC 6 Zigzag conversion	$O(n)$	$O(n)$ for the output
LC 1041 Robot bounded	$O(n)$ — one pass, not simulated to convergence	$O(1)$
Naive “simulate until it repeats”	unbounded	unbounded

The pattern to notice: every row is linear or quadratic in the input, and the interview question is always the space column. Simulation problems are rarely about finding a cleverer asymptotic bound — they are about doing the obvious thing in place without corrupting the state you are still reading. The exception is the last two rows, where the right move is to stop simulating and find the invariant (four cycles; net displacement) that answers the question directly.

The variant map

Variant	The technique	Canonical problem
Cellular update	Encode next state in spare bits	289
Robot with turns	Direction vectors or the rotation pair	1041 · 874 · 657
Unusual output order	Bucket by target row/column	6 · 54 · 498
Formatting / justification	Careful integer division of spare space	68 · 12 · 273
Enormous step count	Find the cycle, then use modular arithmetic	1041 · 957
Obstacle-aware movement	A set of obstacles for $O(1)$ lookup	874

LC 957 is the cycle argument at full strength

Cell State After N Days runs for up to $N = 10^9$ days — utterly unsimulatable. But there are only 8 cells with fixed end cells, so at most $2^6 = 64$ distinct reachable states, which means the sequence must cycle within 64 steps.

So: simulate while recording each state in a dictionary mapping state to the day it first appeared. On a repeat you have the cycle length, and you can reduce the remaining days modulo it and finish quickly.

That “record states, detect the repeat, reduce modulo the cycle” recipe is the general answer whenever the step count is astronomically large but the state space is small. Recognising which of the two you have been given is the whole skill.

Practice — real LeetCode problems

LC 289 — Game of Life · Medium

Problem. Given an m x n board of 0 (dead) and 1 (live), compute the next state. Each cell’s fate depends on its eight neighbours: a live cell survives with 2 or 3 live neighbours; a dead cell becomes live with exactly 3. All updates happen simultaneously.

Constraints. 1 <= m, n <= 25, cells are 0 or 1.

Examples. [[0,1,0],[0,0,1],[1,1,1],[0,0,0]] becomes [[0,0,0],[1,0,1],[0,1,1],[0,1,0]] · [[1,1],[1,0]] becomes [[1,1],[1,1]]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The requirement is simultaneous update, so the naive in-place loop is wrong: a cell updated early changes what its neighbours observe.

Encoding both states in one integer resolves it. & 1 reads the original value, |= 2 writes the next one, and nothing reads bit 1 during the first pass. A second pass shifts every value right, promoting the future to the present.

Time $O(m \cdot n \cdot 8) = O(mn)$. Space $O(1)$.

[[1]] becoming [[0]] is worth checking: a single live cell has zero live neighbours, so it dies of underpopulation. It is easy to assume a lone cell persists.

The two-pass structure is what makes this correct rather than clever — and the same “defer the write to a place the reader ignores” idea appears in Set Matrix Zeroes, where the borders store the flags.

State the $O(mn)$-space copy first: build a fresh board and read the original. It is simpler, obviously correct, and often all that is wanted. Offer the bit trick as the $O(1)$ answer.

Follow-uups you should expect:

• “What if the board is infinite?” LeetCode asks this directly. Store only the live cells as a set of coordinates, and for each iteration consider live cells plus their neighbours — work proportional to the live population, not the grid. That is the real-world answer.
• “What if it does not fit in memory?” Process in horizontal bands, keeping the boundary rows of adjacent bands so neighbour counts stay correct.
• “More than two states?” Bit encoding still works with more bits, or use larger sentinel values.
• “Why not update in place naively?” Show a concrete cell whose neighbour count changes mid-pass.

LC 1041 — Robot Bounded In Circle · Medium

Problem. A robot starts at (0, 0) facing north and repeats an instruction string forever. "G" moves forward one unit, "L" turns left 90°, "R" turns right 90°. Return True if there is a circle that the robot never leaves.

Constraints. 1 <= len(instructions) <= 100, characters are G, L or R.

Examples. "GGLLGG" gives True (returns to the origin) · "GG" gives False (walks north forever) · "GL" gives True

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Simulating “forever” is impossible, so reason about what one pass does.

After one pass the robot has a net displacement and a net rotation. Two cases:

• Net rotation is zero (still facing north). Every pass then adds the same displacement, so unless that displacement is zero the robot drifts away forever.
• Net rotation is non-zero (90°, 180° or 270°). Four passes compose to a multiple of 360°, and the four displacement vectors — each rotated relative to the last — sum to zero. The robot returns to the origin every four passes and is therefore bounded.

So the test is: back at the origin, or not facing the original direction.

Time $O(n)$, one pass. Space $O(1)$.

The test cases cover each branch:

• "GG" gives False — no rotation, non-zero displacement; the only unbounded shape.
• "GL" gives True — rotated, so bounded even though it moved.
• "GGLLGG" gives True — returns to the origin exactly.
• "GLGLGGLGL" gives False — the case worth tracing; it ends facing north with a non-zero displacement despite containing turns. Net rotation is what matters, not the presence of turns.
• "R" gives True — rotation with no movement at all.
• "GLRLLG" gives True — turns that partially cancel, still leaving a net rotation.

Getting the two rotation formulas the right way round matters. Left is (-dy, dx), right is (dy, -dx). Swapping them mirrors every simulation, and several of these cases would still pass by symmetry — which makes it a nasty bug. "GLGLGGLGL" is the one that discriminates.

Follow-ups you should expect: “Why four passes?” — 90° rotations have order 4, so the composition closes. “What if turns were 60°?” — then six passes; the argument generalises to any rational rotation. “Track the actual bounding radius?” — accumulate the maximum distance over four passes. “Walking Robot Simulation (LC 874)?” — genuine step-by-step simulation, with obstacles in a set for $O(1)$ lookup.

LC 6 — Zigzag Conversion · Medium

Problem. Write the string s in a zigzag pattern over numRows rows, then read it off row by row.

Constraints. 1 <= len(s) <= 1000, 1 <= numRows <= 1000, s is letters, , and ..

Examples. "PAYPALISHIRING", 3 gives "PAHNAPLSIIGYIR" · "PAYPALISHIRING", 4 gives "PINALSIGYAHRPI" · "A", 1 gives "A"

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

You never need the grid — only which row each character lands in. Walk the string once, appending to the current row’s bucket, and flip direction at the boundaries.

Time $O(n)$. Space $O(n)$ for the output.

Three details:

• numRows == 1 must be guarded. With one row, row == 0 and row == numRows - 1 are both true. The if row == 0 branch wins, sets step = 1, and row becomes 1 — out of range on the next append. Returning s unchanged is both safe and correct.
• Check row == 0 first. The ordering resolves the ambiguous single-row case deterministically, which is what makes the guard sufficient.
• numRows may exceed the string length. ("AB", 5) gives "AB": the walk never reaches the bottom, so step stays 1, characters land in rows 0 and 1, and the empty rows contribute nothing to the join. No special handling needed.

("ABCD", 2) giving "ACBD" is the smallest genuine zigzag: rows are A, C and B, D.

Building a list of lists and joining is markedly faster in Python than repeated string concatenation, which is $O(n)$ per operation because strings are immutable.

The alternative approach computes each row’s indices directly with the cycle length 2 * numRows - 2 and a formula per row. It is $O(n)$ too and avoids the state variable, but the index arithmetic for the middle rows — which receive two characters per cycle — is easy to get wrong under pressure. The bouncing step is harder to break.

Follow-ups you should expect: “Do it with index arithmetic instead?” — the cycle-length formula; mention the two-per-cycle subtlety for middle rows. “Reverse the transformation?” — decode by reconstructing the same row assignment and reading back. “Why not a 2D grid?” — $O(n \cdot \text{numRows})$ space, mostly empty. “Text Justification (LC 68)?” — the same genre, harder: distribute spare spaces left-to-right with integer division, and left-justify the final line.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 68 is the honest test of care

Text Justification has no algorithmic content and is Hard purely on case density:

• Greedily fit as many words per line as possible.
• Distribute spare spaces left to right, so earlier gaps get the extra space — divmod(spaces, gaps) gives the base and the remainder.
• A line with a single word is left-justified and padded on the right.
• The final line is always left-justified, single-spaced.

There is no shortcut. What is being measured is whether you enumerate the cases before coding rather than discovering them one failed submission at a time — which is exactly the habit the edge-case checklists on these pages are meant to build.

6 problems

1 easy4 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○657Robot Return to OrigineasyJust count opposing moves; no simulation needed
• ○6Zigzag ConversionmediumBouncing step; guard `numRows == 1`LeetCode Top Interview 150
• ○289Game of LifemediumTwo-bit encoding for simultaneous in-place updateLeetCode Top Interview 150
• ○874Walking Robot SimulationmediumGenuine simulation; obstacles in a `set` for $O(1)$ lookup
• ○1041Robot Bounded In CirclemediumOne pass + a rotation argument -- do not simulate forever
• ○68Text JustificationhardPure specification-following; the last line is left-justifiedLeetCode Top Interview 150

Interview follow-ups

They ask	What they’re checking	The answer
“Should you simulate at all?”	The most important judgement	Not when the step count is huge — find a cycle, a closed form, or an invariant
“How do you handle simultaneous updates?”	The in-place trick	Encode the next state in spare bits, read with & 1, write with |= 2, then shift
“How do you rotate a direction?”	Fluency	(-dy, dx) for left, (dy, -dx) for right; or a clockwise DIRS list with ± 1 mod 4
“Why four passes for LC 1041?”	The cycle argument	90° rotations have order 4, so four passes compose to a closed loop
“What if the board were infinite?”	Real-world scaling	Store only live cells in a set; work scales with the live population
“Why not build the 2D grid for zigzag?”	Space awareness	$O(n \cdot \text{numRows})$ and mostly empty; buckets per row are $O(n)$
“How do you avoid off-by-ones here?”	Method	Enumerate the boundary cases before coding, and pick the formulation with fewer branches

Edge-case checklist

• Single cell / single character — [[1]] dies; "A" with 1 row returns itself.
• numRows == 1 (LC 6) — must be guarded or it raises.
• numRows greater than len(s) — ("AB", 5) gives "AB"; empty rows contribute nothing.
• A lone live cell (LC 289) — dies of underpopulation; not obviously so.
• All cells dead / all alive — the trivial extremes.
• Instructions with no G (LC 1041) — "R" gives True, never moving.
• Instructions with no turns — "GG" gives False, the only unbounded shape.
• Turns that cancel to zero net rotation — "GLGLGGLGL" gives False; net rotation is what counts, not the presence of turns.
• Left/right rotation formulas swapped — mirrors everything, and several cases still pass by symmetry.
• Boundary reads (LC 289) — corner cells have only 3 neighbours; bound-check every offset.

Self-check

pch.quizTag Simulation and stateful iteration — self-check

1. Why can't Game of Life update cells in place with a single value each?

   A Because the board may be empty B Because every cell's next state depends on its neighbours' CURRENT state — writing as you read means later cells see a half-updated generation C Because the rules use eight neighbours D Because Python lists are immutable
   pch.quizShowAnswer

   B — Because every cell's next state depends on its neighbours' CURRENT state — writing as you read means later cells see a half-updated generation — This is the defining hazard of grid simulation, and it is why the tick boundary matters. Copying the board is the correct O(mn)-space answer; the two-bit encoding is the in-place one.

2. In the two-bit trick, why is `board[nr][nc] & 1` correct even for a neighbour already carrying a future bit?

   A Because bit 1 is cleared after each read B Because masking with 1 extracts only the CURRENT state — a cell holding binary 10 reads as 0, which is its present value C Because neighbours are visited in order D It is not; that is why two passes are needed
   pch.quizShowAnswer

   B — Because masking with 1 extracts only the CURRENT state — a cell holding binary 10 reads as 0, which is its present value — The encoding is what makes one array sufficient: bit 0 stays the untouched present throughout pass 1, and pass 2 shifts everything right to promote the future.

3. Why use a `directions` list rather than four explicit if-blocks?

   A It is faster B Because the neighbour logic is written once and the offsets become data — switching from 4-directional to 8-directional, or to knight moves, becomes a one-line change to the list C Because tuples use less memory D Because it avoids bounds checks
   pch.quizShowAnswer

   B — Because the neighbour logic is written once and the offsets become data — switching from 4-directional to 8-directional, or to knight moves, becomes a one-line change to the list — Four copies of near-identical code is four chances to typo one, and it is the reason the 4-versus-8 neighbour variants of these problems are so error-prone when hand-unrolled.

4. LC 1041 asks whether a robot's path is bounded. Why not simulate until it repeats?

   A Because the robot may never repeat B Because four cycles always restore the original orientation — so one pass over the instructions is enough: not facing north means bounded, facing north means bounded only if net displacement is (0,0) C Because simulation would be O(n²) D Because the instructions may be empty
   pch.quizShowAnswer

   B — Because four cycles always restore the original orientation — so one pass over the instructions is enough: not facing north means bounded, facing north means bounded only if net displacement is (0,0) — This is the 'do not simulate' case. Finding the invariant that collapses unbounded time into one pass is a distinct skill from executing the simulation carefully.

5. Rotating an n×n image in place — what is the two-step recipe?

   A Rotate each ring one element at a time B Transpose (swap across the main diagonal), then reverse each row — two simple passes instead of four-way cyclic swaps C Reverse each column, then transpose the result twice D Copy to a new matrix; in place is impossible
   pch.quizShowAnswer

   B — Transpose (swap across the main diagonal), then reverse each row — two simple passes instead of four-way cyclic swaps — Ring-by-ring four-way swaps also work and are far easier to get wrong. Transpose-then-reverse is O(1) space and each step is independently checkable.

6. The Game of Life board is now infinite. What changes?

   A Nothing; use a bigger array B The representation, not the rule: keep only live cells in a set, count neighbours with a Counter over their neighbourhoods, and the grid dimensions leave the problem entirely C The rule becomes probabilistic D It becomes unsolvable
   pch.quizShowAnswer

   B — The representation, not the rule: keep only live cells in a set, count neighbours with a Counter over their neighbourhoods, and the grid dimensions leave the problem entirely — A standard follow-up, and the answer generalises: when a grid is sparse or unbounded, store the interesting cells rather than the grid.

Recall card

• Cue — the problem describes a process: rotate, spiral, tick, bounce, walk, refill. No clever algorithm is implied; the difficulty is executing it exactly.
• Direction vectors — one directions list, one loop. Never four copies of the neighbour logic.
• Read-then-write — a cell whose next state depends on neighbours must not be overwritten while others still read it. Copy the grid ($O(mn)$), or encode both states in one value (bit 0 = present, bit 1 = future, then shift) for $O(1)$.
• Rotate in place — transpose, then reverse each row.
• State machines — direction as an index into a cycle (d = (d + 1) % 4), so turning is arithmetic rather than branching.
• Do not simulate when time is unbounded — find the invariant. LC 1041: four cycles restore the original heading, so one pass over the instructions decides it.
• Cost — nearly always $O(mn)$ or $O(n)$ time; the interview question is the space column, and getting to $O(1)$ without corrupting live state is the whole exercise.
• Sparse or infinite grids — store the live cells in a set, not the grid.

Recap

• Some problems have no trick, and the skill is faithful translation of the specification plus disciplined case enumeration.
• Direction vectors or the rotation pair ((-dy, dx) left, (dy, -dx) right) replace four-branch if chains. Python’s non-negative % makes (i - 1) % 4 safe.
• For simultaneous updates, encode the next state in spare bits — read with & 1, write with |= 2, then shift. Offer the $O(mn)$ copy first; the bit trick is the $O(1)$ follow-up.
• A bouncing step variable beats modular index arithmetic for zigzag traversal — and numRows == 1 must be guarded explicitly.
• The most valuable instinct is not simulating. When the step count is huge but the state space is small, find the cycle and reduce modulo its length. LC 1041 needs one pass and a rotation argument; LC 957 needs cycle detection.
• Build strings by joining a list, never by repeated concatenation.

Next: the advanced graph algorithms — MST, strongly connected components, and max flow.