Simulation

Topic type: Technique-Based | LeetCode problems: 200+

---

Core Concepts

Simulation — directly executing the rules described in a problem statement step by step, producing the correct final state without a mathematical shortcut. The solution IS the described process.

State — the complete information needed to determine the next step; may be a single variable, a grid, a queue, or multiple interdependent structures. Every simulation maintains and transitions state.

State transition — the function mapping the current state to the next given one event or time step. Identifying the transition rule exactly is the central challenge of every simulation problem.

Tick / time step — the unit of forward progress in the simulation; one "round", one "move", or one "second". Problems may simulate a fixed number of ticks or run until a termination condition.

Termination condition — the predicate that stops the simulation: a target reached, no more moves possible, a cycle detected, or a fixed end time elapsed.

Cycle detection — recognising that the state has returned to a previously seen configuration; once a cycle is found, the answer for any future tick can be computed with modular arithmetic instead of simulating further.

In-place vs. copy update — when next state depends on the current state of neighbours (not the already-updated neighbours), updates must be applied simultaneously. Strategies: (a) write to a fresh copy then swap, or (b) encode old and new state together in one cell value.

Boundary / wrap-around — many simulations occur on a bounded grid (clamp coordinates) or a toroidal grid (modular coordinates). Knowing which applies changes every boundary check.

Command / instruction stream — problems that supply a sequence of operations to apply in order; the simulation processes each instruction and maintains the resulting state.

---

Types / Variants

---

Key Algorithms

Direct Step-by-Step Execution

Execute the stated rules for each tick, updating state accordingly. The correctness argument is trivial: the code is the spec. Time complexity is O(ticks × cost_per_tick); the challenge is minimising cost_per_tick through efficient state representation. Space is O(state_size).

Simultaneous Update via Copy

When next state of cell i depends on current (pre-update) neighbours, copy the grid, compute new values from the copy, then replace.

new_grid = [row[:] for row in grid]
# write to new_grid, read from grid
grid = new_grid

Time O(state_size) per tick. Simpler than in-place encoding; preferred unless O(1) space is explicitly required.

Simultaneous Update via In-Place Bit Encoding

Encode old state in bit 0 and new state in bit 1 of each cell value. Read old state as cell & 1; write new state to bit 1 as cell |= (new_val << 1). After all cells processed, shift right: cell >>= 1.

# read old, write new into bit 1
grid[r][c] |= (new_state << 1)
# decode
grid[r][c] >>= 1

O(1) extra space. Use only when the problem explicitly demands in-place O(1) space.

Cycle Detection (Floyd or Hashing)

After simulating each tick, hash the full state and store it in a dictionary mapping state → tick_number. When a repeated state is found, the remaining ticks can be resolved with modulo.

seen = {}
while tick < target:
    key = state_hash(state)
    if key in seen: break
    seen[key] = tick; tick += 1; advance(state)
remaining = (target - tick) % (tick - seen[key])

Time O(cycle_length × cost_per_tick); avoids simulating billions of ticks for periodic problems.

Direction Array + Position Tracking

For movement simulations, maintain pos = (r, c) and dir_idx into a direction array. Turning left or right adjusts dir_idx modulo 4.

dirs = [(0,1),(1,0),(0,-1),(-1,0)]  # E S W N
dir_idx = (dir_idx + 1) % 4  # turn right
r, c = r + dirs[dir_idx][0], c + dirs[dir_idx][1]

This pattern handles all rotation-based movement problems uniformly.

Digit-by-Digit Arithmetic Simulation

Process two numeric strings right-to-left, maintaining a carry. Append digits to a result list, then reverse.

i, j, carry = len(a)-1, len(b)-1, 0
while i >= 0 or j >= 0 or carry:
    s = carry + (int(a[i]) if i>=0 else 0) + (int(b[j]) if j>=0 else 0)
    result.append(s % 10); carry = s // 10; i -= 1; j -= 1

O(max(n, m)) time. Applies to Add Strings, Add Binary, Multiply Strings (with the outer loop).

Queue-Based Process Simulation

Use collections.deque to model a circular queue of tasks, a cooldown window, or a round-robin scheduler. Enqueue tasks in order; pop from front; re-enqueue if work remains. Time O(total_work); space O(number_of_task_types or queue_size).

Spiral / Path Tracing with Boundary Pointers

Four boundary variables top, bottom, left, right shrink as each layer is consumed. The spiral continues while top <= bottom and left <= right.

See matrix.md for the full spiral traversal algorithm and its boundary-pointer mechanics.

String Decode / Encode Simulation

Scan the string character by character, using a stack to handle nested structures (e.g., k[encoded_string] recursion in Decode String). Push current string and count when [ is encountered; pop and repeat on ].

stack, cur, k = [], "", 0
for ch in s:
    if ch == '[': stack.append((cur, k)); cur, k = "", 0
    elif ch == ']': prev, n = stack.pop(); cur = prev + cur * n

O(output_length) time.

---

Advanced Techniques

State Compression for Cycle Detection

Problem class: Simulations on grids or arrays that must run for 10⁸+ ticks (e.g., cycle after N billion steps). Mechanism: Convert the entire state to a hashable key (tuple of tuples for grids, tuple for arrays). Store key → tick in a dict. On collision, the period is tick - seen[key]; compute answer with (target - tick) % period remaining steps. When to prefer over direct simulation: whenever target_ticks is astronomically large but the state space is bounded — direct simulation would TLE; cycle detection runs in at most state_space_size ticks. Complexity: O(S · T) where S = state_size and T = cycle_length; far less than O(target_ticks · S) for large targets.

Lazy / Deferred Update with Difference Array

Problem class: Simulations where many range updates (add v to positions i..j) happen and only the final state is needed — not intermediate values. Mechanism: Apply each range update as two point writes on a difference array (d[i] += v, d[j+1] -= v), then compute a prefix sum once at the end. Avoids O(n) per update. When to prefer over direct range update: when there are k range updates each spanning O(n) positions — direct update costs O(kn); difference array costs O(k + n). Complexity: O(k + n) total vs. O(kn) naive.

See prefix-sum.md for 1D and 2D difference array mechanics.

Event-Driven Simulation (Skipping Empty Time)

Problem class: Scheduling or queue problems where ticks with no activity are plentiful (sparse event stream). Mechanism: Instead of advancing one tick at a time, jump directly to the next event time using a priority queue or sorted event list. Only process ticks when something actually happens. When to prefer over tick-by-tick: when the time range is large (up to 10⁹) but the number of events is small (≤ 10⁵) — tick-by-tick would TLE; event-driven processes only the O(events) meaningful moments. Complexity: O(E log E) for E events vs. O(T) tick-by-tick for T total time units.

Multi-Pointer / Multi-Agent Simultaneous Advance

Problem class: Simulations with multiple independent agents (robots, pointers, particles) that all move simultaneously each tick. Mechanism: Compute all agents' new positions before applying any updates (simultaneous semantics). Detect collisions or merges after the full-tick advance. Distinguish "agents pass through each other" from "agents collide and stop". When to prefer over agent-by-agent advance: whenever the problem specifies simultaneous movement — advancing one agent at a time changes collision outcomes and produces wrong answers. Complexity: O(A) per tick for A agents, same asymptotic but semantics are different.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Reading updated neighbours during simultaneous update — if you update grid[r][c] before reading grid[r][c+1], the neighbour count for grid[r][c+1] is wrong because it sees the new value. Always read from the original state (use a copy or encode old+new in the same cell).

• Off-by-one in tick count — "after N steps" usually means simulate N transitions, not N+1. Similarly, "N rounds" ending at round N vs. round N−1 is a common source of wrong answers. Trace a small example manually before coding.

• Cycle detection starting point — the cycle may not start at tick 0 (the sequence may have a "tail" before it becomes periodic). The correct formula for the answer at tick T (where cycle starts at tick start with period period) is: if T < start, simulate directly; else answer = state at tick start + (T - start) % period.

• Direction index wrapping — turning left is (dir_idx - 1) % 4, not dir_idx - 1. In Python (-1) % 4 == 3, so this is safe, but explicitly using % 4 makes intent clear and prevents bugs in languages where % is not always positive.

• Carry left over after loop — in digit arithmetic, when carry > 0 after the main loop exits (both digit strings exhausted), that carry must still be appended. Forgetting this produces a result one digit too short.

• String concatenation inside a loop — building a result string with result += char is O(n²) in Python (each += allocates a new string). Use result.append(char) on a list then ''.join(result) at the end.

• Mutable default state shared across calls — if the initial state (e.g., a grid or list) is created once and reused across simulation steps without resetting, subsequent calls see corrupted state. Always create fresh state at the start of each simulation run.

• Simultaneous agent collision semantics — "agents moving simultaneously" means positions are swapped atomically. If agent A moves to B's old position and B moves to A's old position, they have passed through each other (not collided), depending on the problem's definition. Confirm the collision rule before coding.

• Integer overflow in carry multiplication — in Multiply Strings, each intermediate product digit_a * digit_b can be at most 81, which fits in a 32-bit integer, but accumulated sums over many digits can exceed it. Use Python's arbitrary-precision integers or explicit modular arithmetic in other languages.

• Gravity direction mismatch — in "falling" problems, which direction is "down" depends on the problem. Applying the gravity scan in the wrong direction produces a valid-looking but wrong result. Re-read the problem to confirm the axis and direction.

• Deque vs. list for queue simulation — using list.pop(0) is O(n) and makes an O(N·k) simulation O(N·k·n). Always use collections.deque with popleft().

---

Implementation Notes

• collections.deque is required for queue-based simulations; list.pop(0) is O(n) and causes TLE on large inputs.
• Python integers are arbitrary-precision, so multi-digit arithmetic simulations do not overflow; in Java/C++ you must track carry explicitly to avoid 32-bit overflow.
• divmod(x, base) returns (quotient, remainder) in one call; use it in digit arithmetic loops to get the next digit and carry simultaneously.
• For cycle detection on grids, tuple(tuple(row) for row in grid) produces a hashable key; do not use str(grid) as it is slower and can collide for different grid shapes.
• heapq in Python is a min-heap; for event-driven simulations, push (event_time, data) tuples directly — ties are broken by the second element, so include a tiebreaker if event ordering matters.
• Modular indexing for toroidal grids: always (r + dr) % m rather than manually clamping; Python's % is always non-negative, so this is safe even for negative dr.
• When encoding two states in one cell value, restrict old state to bit 0 (values 0 or 1) and new state to bit 1 (values 0 or 2) before combining; values outside {0, 1, 2, 3} indicate a logic error.
• sys.setrecursionlimit is not needed for simulation problems since they are almost always iterative; if you find yourself writing recursive simulation, consider converting to an explicit stack or loop.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Cellular automaton / grid update

• Game of Life (289) — simultaneous 8-neighbour update; in-place bit encoding; classic simultaneous-update problem
• Conway's Game of Life infinite board (289 follow-up) — sparse grid with dict; only track live cells and their neighbours

Movement / navigation

• Walking Robot Simulation (874) — direction array with turns; obstacle set; track max distance
• Robot Return to Origin (657) — count net displacement; cancel opposite moves
• Spiral Matrix (54) — read grid in spiral order; four-pointer boundary shrink
• Spiral Matrix II (59) — write 1..n² in spiral; same pattern

Arithmetic simulation

• Add Strings (415) — right-to-left digit scan with carry; foundational
• Add Binary (67) — same pattern on binary digits
• Multiply Strings (43) — O(n·m) double loop; intermediate result array; carry propagation at end
• Plus One (66) — single-array carry propagation; all-9s edge case

Scheduling / queue simulation

• Task Scheduler (621) — cooldown-aware scheduling; greedy slot computation or queue simulation
• Design Hit Counter (362) — sliding-window count; queue-based simulation
• Design Circular Queue (622) — implement queue operations with a fixed array and two pointers

String construction / decode

• Decode String (394) — stack-based; nested k[encoded] with arbitrary depth
• Text Justification (68) — simulate line-by-line word packing; even-space distribution; last-line special case
• Count and Say (38) — run-length encode the previous term; straightforward simulation
• String Compression (443) — in-place run-length encoding with two pointers

Falling / gravity

• Falling Dominoes (838) — scan left-to-right and right-to-left; track force magnitude
• Gravity (Tetris-style, LeetCode 2048 / matrix gravity variants) — scan column from bottom; compact non-zero cells

Large-N periodic

• Prison Cells After N Days (957) — 8-cell state; cycle period ≤ 256; detect cycle, apply modulo
• Rotating the Box (1861) — apply gravity then rotation; order of operations matters
• Simulate N ticks of a 1D automaton (various) — detect repeating state; cycle length typically << N

Multi-digit / range-update

• Range Addition (370) — difference array; apply k range updates in O(k), reconstruct in O(n)
• Car Fleet (853) — sort by position; simulate each car's arrival; stack to track fleets

Clarification Questions to Ask

• Does "simultaneously" mean all agents/cells update at the same time, or do updates propagate immediately? (Changes whether you need a copy.)
• What happens at boundaries — does the agent stop, wrap around, or reflect?
• Is N (number of steps) guaranteed small enough to simulate directly, or can it be 10⁹+?
• For collision problems: do agents pass through each other, stop, merge, or annihilate?
• For arithmetic simulations: are inputs guaranteed non-negative? Can they be zero or have leading zeros?
• For scheduling: are all task types enumerated upfront, or can new types arrive?
• For string formatting: can a single word exceed the line width (and if so, how to handle it)?

Common Interview Mistakes

• Updating cells in-place during simultaneous grid simulation — reading an already-updated neighbour corrupts the count for the next cell processed.
• Forgetting the final carry digit in addition/multiplication — produces a result that is off by one digit for cases like 999 + 1.
• Using direct simulation for N = 10⁹ steps — TLEs without cycle detection; always check the size of N before choosing the approach.
• Using list.pop(0) instead of deque.popleft() — O(n) per pop turns O(N) simulation into O(N²).
• Turning with dir_idx - 1 without % 4 — works in Python but breaks in languages where % on negatives is negative; always use modular arithmetic.
• Incorrect cycle detection formula — applying T % period without accounting for the pre-cycle tail gives wrong state. Must compute (T - tail_length) % period and simulate the tail separately.
• Building result string with += inside a loop — O(n²) total; use a list and ''.join().
• Misidentifying the gravity direction — scanning in the wrong direction produces a plausible-looking wrong result; verify with a small example.

Typical Follow-Up Escalations

• "Now simulate on an infinite grid" → switch from 2D array to a dict of {(r,c): state} keyed on live cells only; only iterate over live cells and their neighbours.
• "Now N can be up to 10¹⁸" → cycle detection is mandatory; describe hashing the state and computing modulo within the cycle.
• "Now multiple simultaneous arithmetic operations, results needed online" → consider BigInteger data structure or streaming carry approaches.
• "Now queries arrive online: after each command, report current state" → maintain state incrementally rather than re-simulating from scratch; identify what changes per command.
• "Can you do it in O(1) extra space?" → in-place bit encoding for grid automata; difference array (O(n) but not O(state²)) for range-update simulations.
• "What is the minimum number of steps to reach a target configuration?" → BFS over state space with each simulated step as an edge; state = full configuration.