LeetCode 874: Walking Robot Simulation

Problem Restatement

A robot starts at:

(0, 0)

on an infinite XY-plane.

It starts facing north.

The robot receives commands:

There are also obstacles on the grid.

If the robot tries to move onto an obstacle, it stays in its current position and moves to the next command.

Return the maximum squared Euclidean distance from the origin that the robot reaches at any point.

The squared distance from (x, y) is:

x * x + y * y

Input and Output

Function shape:

class Solution:
    def robotSim(self, commands: list[int], obstacles: list[list[int]]) -> int:
        ...

Examples

Example 1:

commands = [4, -1, 3]
obstacles = []

The robot starts at (0, 0) facing north.

It moves north 4 units:

(0, 4)

Then it turns right and faces east.

It moves east 3 units:

(3, 4)

The maximum squared distance is:

3 * 3 + 4 * 4 = 25

So the answer is:

25

Example 2:

commands = [4, -1, 4, -2, 4]
obstacles = [[2, 4]]

The robot moves north to (0, 4).

Then it turns right and tries to move east 4 units.

The obstacle is at (2, 4), so the robot can only move to:

(1, 4)

Then it turns left and moves north to:

(1, 8)

The maximum squared distance is:

1 * 1 + 8 * 8 = 65

So the answer is:

65

Example 3:

commands = [6, -1, -1, 6]
obstacles = [[0, 0]]

There is an obstacle at the origin.

The robot ignores it while starting there, but once it leaves, it cannot return to (0, 0).

The robot reaches (0, 6), then turns around and moves south until it is blocked before the origin.

The maximum squared distance is:

36

First Thought: Direct Simulation

This problem asks us to follow the commands exactly.

So simulation is the right approach.

The only part that needs care is obstacle handling.

When a command says:

move forward k units

we cannot jump directly by k.

An obstacle may be in the middle of the path.

So we must move one unit at a time.

Key Insight

Use direction vectors for the four directions.

Store them in clockwise order:

directions = [
    (0, 1),    # north
    (1, 0),    # east
    (0, -1),   # south
    (-1, 0),   # west
]

Keep a direction index:

direction = 0

where 0 means north.

Turning right moves to the next direction:

direction = (direction + 1) % 4

Turning left moves to the previous direction:

direction = (direction - 1) % 4

For obstacles, use a set of coordinate pairs:

obstacle_set = {(x, y), ...}

This lets us check blocked cells in expected O(1) time.

Algorithm

Create a set of obstacles.

Initialize:

x = 0
y = 0
direction = 0
answer = 0

For each command:

1. If the command is -1, turn right.
2. If the command is -2, turn left.
3. Otherwise, move forward one step at a time:
   1. Compute the next cell.
   2. If the next cell is an obstacle, stop this command.
   3. Otherwise, move there.
   4. Update the maximum squared distance.

Return answer.

Correctness

The algorithm processes commands in the given order.

For turn commands, it updates the direction index according to the required 90-degree rotation.

For movement commands, it attempts exactly one unit move at a time. Before entering a cell, it checks whether that cell is an obstacle. If it is blocked, the robot stays in its current position and stops processing the current movement command, which matches the problem rule.

If the cell is not blocked, the algorithm updates the robot position exactly as the command requires.

After each successful move, the algorithm computes the squared distance from the origin and keeps the maximum value seen.

Therefore, every position reached by the simulated robot is exactly a position the real robot reaches, and the maximum squared distance returned is correct.

Complexity

Let:

m = len(commands)
o = len(obstacles)

Each forward command moves at most 9 steps.

Implementation

class Solution:
    def robotSim(self, commands: list[int], obstacles: list[list[int]]) -> int:
        obstacle_set = {(x, y) for x, y in obstacles}

        directions = [
            (0, 1),
            (1, 0),
            (0, -1),
            (-1, 0),
        ]

        x = 0
        y = 0
        direction = 0
        answer = 0

        for command in commands:
            if command == -1:
                direction = (direction + 1) % 4

            elif command == -2:
                direction = (direction - 1) % 4

            else:
                dx, dy = directions[direction]

                for _ in range(command):
                    next_x = x + dx
                    next_y = y + dy

                    if (next_x, next_y) in obstacle_set:
                        break

                    x = next_x
                    y = next_y

                    answer = max(answer, x * x + y * y)

        return answer

Code Explanation

We first store obstacles in a set:

obstacle_set = {(x, y) for x, y in obstacles}

This makes obstacle lookup fast.

The direction list stores movement vectors:

directions = [
    (0, 1),
    (1, 0),
    (0, -1),
    (-1, 0),
]

The robot starts at the origin, facing north:

x = 0
y = 0
direction = 0

A right turn moves clockwise:

direction = (direction + 1) % 4

A left turn moves counterclockwise:

direction = (direction - 1) % 4

For a forward command, get the current movement vector:

dx, dy = directions[direction]

Then move one unit at a time:

for _ in range(command):

Before moving, check the next cell:

if (next_x, next_y) in obstacle_set:
    break

If the next cell is clear, update the robot position:

x = next_x
y = next_y

Then update the best squared distance:

answer = max(answer, x * x + y * y)

Testing

def test_robot_sim():
    s = Solution()

    assert s.robotSim([4, -1, 3], []) == 25

    assert s.robotSim(
        [4, -1, 4, -2, 4],
        [[2, 4]],
    ) == 65

    assert s.robotSim(
        [6, -1, -1, 6],
        [[0, 0]],
    ) == 36

    assert s.robotSim(
        [1, 2, 3],
        [],
    ) == 36

    assert s.robotSim(
        [2, -1, 2, -1, 2, -1, 2],
        [],
    ) == 8

    assert s.robotSim(
        [2, 2, 2],
        [[0, 3]],
    ) == 4

    print("all tests passed")

test_robot_sim()

Test meaning: