Walking Robot Simulation: Grid Traversal with Obstacle Avoidance

LeetCode 874, Walking Robot Simulation, puts a robot at the origin of an infinite 2D grid facing north. You are given an array of commands and a list of obstacle coordinates. Each command is either a positive integer (move forward that many steps), -1 (turn right 90 degrees), or -2 (turn left 90 degrees). The robot stops before hitting any obstacle. Return the maximum squared Euclidean distance from the origin that the robot reaches at any point during its walk.

The trick is not simulating anything fancy. You walk one step at a time, check for obstacles using a hash set, and track the farthest point you have seen.

Why this problem matters

Walking Robot Simulation teaches two patterns that show up everywhere in grid problems. The first is the direction vector array, where you encode north, east, south, and west as (dx, dy) offsets and rotate by changing an index. The second is using a hash set for O(1) coordinate lookups instead of scanning through a list every time you need to check a position.

These two building blocks combine to solve this problem cleanly, and they transfer directly to any problem involving movement on a grid with obstacles or boundaries.

The approach

1. Convert the obstacle list into a set of (x, y) tuples for O(1) lookup.
2. Define a direction array: [(0, 1), (1, 0), (0, -1), (-1, 0)] for north, east, south, west.
3. Start at position (0, 0) facing north (direction index 0).
4. For each command:
   • If -1, turn right by incrementing the direction index modulo 4.
   • If -2, turn left by decrementing the direction index modulo 4.
   • If positive, take that many single steps in the current direction, stopping early if the next cell is an obstacle.
5. After each step, update the maximum squared distance if the current position beats it.
6. Return the maximum squared distance.

The solution

def robot_sim(commands, obstacles):
    obstacle_set = set(map(tuple, obstacles))
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    x, y, di = 0, 0, 0
    max_dist = 0

    for cmd in commands:
        if cmd == -1:
            di = (di + 1) % 4
        elif cmd == -2:
            di = (di - 1) % 4
        else:
            for _ in range(cmd):
                nx, ny = x + dx[di], y + dy[di]
                if (nx, ny) in obstacle_set:
                    break
                x, y = nx, ny
                max_dist = max(max_dist, x * x + y * y)

    return max_dist

Visual walkthrough

Let's trace through commands = [4, -1, 4] with obstacles = [[2, 4]]. The robot starts at the origin facing north, walks 4 steps up, turns right to face east, then tries to walk 4 steps east but gets blocked by the obstacle at (2, 4).

Complexity analysis

Time is O(n + k), where n is the total number of steps the robot takes across all commands and k is the number of obstacles. Building the obstacle set takes O(k). Each move command walks up to its value in single steps, and each step does a constant-time set lookup. In the worst case, the robot takes up to 9 steps per command (since each command value is between 1 and 9), so the total steps are bounded by 9 times the number of commands.

Space is O(k) for the obstacle hash set. The direction arrays and position variables use O(1) additional space.

Building blocks

1. Direction vector array

Encoding compass directions as (dx, dy) pairs in a fixed-order array lets you rotate by simply changing an index. Right turn: increment modulo 4. Left turn: decrement modulo 4. This avoids messy if-else chains and makes it trivial to add diagonal directions later. You will see this exact pattern in spiral matrix traversal, snake games, and any grid problem involving turns.

2. Hash set for coordinate lookup

When you need to repeatedly check whether a specific (x, y) position is blocked, storing coordinates in a set gives you O(1) lookups. The naive approach of scanning through the obstacle list on every step would be O(k) per step, which adds up fast. Converting the list to a set once at the start is the standard move.

Edge cases to watch for

• No commands: the robot stays at the origin. Return 0.
• No obstacles: the robot walks freely. The answer is just the farthest point reached.
• All turn commands: if every command is -1 or -2, the robot spins in place. Return 0.
• Obstacle directly ahead: the robot takes zero steps for that command and stays at its current position.
• Obstacle at the origin: the origin is the starting position, not a destination. The robot starts there, so an obstacle at (0, 0) does not block the start. It would only block the robot from returning to the origin later.
• Maximum distance in the middle: the farthest point might not be the final position. You need to track the max across all intermediate positions, not just the ending position.

From understanding to recall

The solution code is short, but the details matter under pressure. Which index is north? Does turning right increment or decrement? Do you check the obstacle before or after moving? These small decisions are easy to get wrong when you are writing from memory in an interview.

Spaced repetition locks in the direction vector pattern and the obstacle set pattern as separate building blocks. Once you can write the direction array and the step-by-step movement loop without thinking, this problem and every problem like it becomes a matter of assembly rather than invention.

Related posts

• Robot Return to Origin - A simpler grid simulation where you only track final position
• Number of Islands - Grid traversal with direction vectors and visited tracking
• Flood Fill - Another grid problem that uses the same neighbor generation pattern