Direct Simulation

Direct Simulation

Some problems don't require a clever algorithm. They require you to do exactly what the problem says, step by step, without missing a boundary or an edge case. These are simulation problems, and they show up in interviews more than people expect. Spiral Matrix is the textbook example, but the category stretches to Game of Life, Zigzag Conversion, and Robot Bounded in Circle. The skill being tested is not algorithmic insight. It's disciplined state management.

What Makes a Problem a Simulation

A simulation problem gives you a set of rules and asks you to follow them. There's no recurrence relation to discover, no invariant to exploit. You move through the structure according to the stated process and collect or mutate values along the way. The challenge is that the rules interact with boundaries in ways that create subtle off-by-one errors, missed termination conditions, or accidental overwrites.

You're looking at a simulation when the problem describes a traversal pattern (spiral, diagonal, zigzag), a physical or cellular process (Game of Life's birth-and-death rules, a robot following commands), or any scenario where "just simulate it" is the entire strategy.

Spiral Matrix: The Canonical Example

Spiral Matrix (LC 54) asks you to return all elements of an m × n matrix in spiral order: left to right across the top, down the right side, right to left across the bottom, up the left side, then repeat inward. The process is well-defined. The difficulty is tracking when to stop and how to shrink the active region after each pass.

The cleanest approach uses four boundary variables, top, bot, left, right, that close inward as each edge is consumed. After traversing the top row, increment top. After the right column, decrement right. After the bottom row (if it still exists), decrement bot. After the left column (if it still exists), increment left. The loop continues while top <= bot and left <= right.

#### Walking Through a 3×4 Matrix

Start with this matrix:

 1  2  3  4
 5  6  7  8
 9 10 11 12

Initial boundaries: top=0, bot=2, left=0, right=3.

Pass 1, traverse top row left to right: collect 1, 2, 3, 4. Then top becomes 1. Traverse right column top to bottom: collect 8, 12. Then right becomes 2. Traverse bottom row right to left (top=1 <= bot=2): collect 11, 10, 9. Then bot becomes 1. Traverse left column bottom to top (left=0 <= right=2): collect 5. Then left becomes 1.

Pass 2, boundaries are now top=1, bot=1, left=1, right=2. Traverse top row: collect 6, 7. top becomes 2. Now top > bot, so the remaining two traversals are skipped (they'd double-count).

Final result: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7].

The guard conditions if top <= bot and if left <= right before the bottom-row and left-column passes are critical. Without them, a matrix with more columns than rows would revisit cells on the final pass.

#### The Code

def spiral_order(matrix):
    if not matrix:
        return []
    res = []
    top, bot = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bot and left <= right:
        for c in range(left, right + 1):
            res.append(matrix[top][c])
        top += 1

        for r in range(top, bot + 1):
            res.append(matrix[r][right])
        right -= 1

        if top <= bot:
            for c in range(right, left - 1, -1):
                res.append(matrix[bot][c])
            bot -= 1

        if left <= right:
            for r in range(bot, top - 1, -1):
                res.append(matrix[r][left])
            left += 1

    return res

Spiral Matrix II (LC 59) is the fill variant: instead of reading values out, you write incrementing integers into the same spiral pattern. The boundary logic is identical: only the operation inside each loop changes.

Other Simulation Problems

Zigzag Conversion (LC 6) asks you to rearrange a string as if it were written diagonally down and then up across a set of rows, then read row by row. The simulation tracks a current row index and a direction flag (+1 or -1). Each character is appended to its row's string. When the row index hits 0 or numRows - 1, the direction flips. Concatenate all rows at the end.

def convert(s, numRows):
    if numRows == 1:
        return s
    rows = ['' for _ in range(numRows)]
    row, direction = 0, 1
    for ch in s:
        rows[row] += ch
        if row == 0:
            direction = 1
        elif row == numRows - 1:
            direction = -1
        row += direction
    return ''.join(rows)

Game of Life (LC 289) is a cellular automaton where each cell lives or dies based on its eight neighbors. The constraint is that all updates must appear simultaneous: a cell updated early in your scan can't influence its neighbors' decisions. One approach is a second matrix. The in-place approach encodes the old state and new state together using extra bit values (e.g., 2 means "was dead, now alive"), then decodes in a second pass.

Robot Bounded in Circle (LC 1041) gives a sequence of commands (go forward, turn left, turn right) and asks whether the robot stays within a bounded region. You simulate one full cycle of commands. The robot is bounded if it ends at the origin or if it's not facing north (any non-north direction after one cycle means the robot traces a closed polygon over multiple cycles).

Why Boundary Handling Is the Real Challenge

The algorithmic heart of every simulation problem is the same: maintain state and apply rules. What trips people up is boundary conditions: the moment the spiral's width collapses to a single row, the moment the zigzag has only one row, the moment a Game of Life cell sits on the grid edge. Each of these requires an explicit check or a safe initialization that prevents an out-of-bounds access or an incorrect computation.

Approach simulation problems methodically: identify every piece of state you need to track, name it explicitly, and ask yourself what happens at each boundary before writing the loop. Trace through a small example by hand before coding. The code itself is usually short once the state is clear.

Complexity

Time complexity for matrix simulations is $O(m \times n)$: every cell is visited exactly once. Space complexity is $O(1)$ beyond the output array, since boundary tracking uses only a fixed number of variables. For Game of Life's in-place variant, the second pass to decode the bit-encoded values keeps it $O(1)$ extra space as well.

Recognizing this pattern

You're probably looking at direct simulation when:

• The problem describes a step-by-step process and asks for the state after k steps or until a terminal condition.
• There's no obvious closed-form shortcut: the rules are the answer.
• A grid is being walked, rotated, or updated in place according to local rules.
• The input itself is small enough that "just do what it says" fits comfortably in the time limit.

Common templates:

• Direction-vector grid walk: keep (dx, dy) and rotate when you hit a boundary or obstacle. Example: Spiral Matrix.
• Local-rule cellular update: read every cell's neighborhood and write the next state, often with bit-packing for in-place. Example: Game of Life.
• Bounded-process detection: simulate a few cycles and check whether the agent returns to the origin or repeats. Example: Robot Bounded In Circle.
• Tick-by-tick state machine: advance a clock, apply rules per element, possibly cap the loop with cycle detection. Example: Rotting Oranges.