Walking Robot Simulation

Problem

We have a robot starting at (0, 0) and facing north on an infinite grid.

Each command means one of three things:

• -2 -> turn left by 90 degrees
• -1 -> turn right by 90 degrees
• 1 to 9 -> move forward that many steps

We are also given obstacle coordinates. If the robot tries to move into an obstacle, it must stop one cell before it and continue with the next command.

The question is not asking for the final distance from the origin. It asks for the maximum squared distance x * x + y * y reached at any moment during the walk.

One small edge case is worth remembering: an obstacle may exist at (0, 0). That does not block the starting position, but it does stop the robot from returning there later.

Intuition

This is a simulation problem, but there is one trap: checking obstacles by scanning the whole obstacles array every time would be too slow.

Instead, we want constant-time obstacle lookup. That is exactly what a hash set gives us.

Because a set needs a single key, we encode each coordinate pair (x, y) into one integer:

hash(x, y) = x + 60013 * y

Why 60013?

• obstacle coordinates are bounded around -30000 to 30000
• choosing a multiplier larger than 60000 keeps different (x, y) pairs unique
• 60013 is also a convenient prime slightly above that range

Once obstacle lookup becomes O(1), the rest is just careful step-by-step movement.

Core Idea

The robot's state is fully described by:

• current position (x, y)
• current direction

We can store directions in this order:

• north
• east
• south
• west

Then a direction index 0..3 is enough.

For every command:

• if it is -1, rotate right
• if it is -2, rotate left
• otherwise move one step at a time

The step-by-step part matters. If a command says move 4, we cannot jump directly by 4 cells because an obstacle may block step 2 or step 3.

Approach

1. Put all obstacles into a hash set using the coordinate hash.
2. Keep a directions array for north, east, south, and west.
3. Track x, y, the current direction index, and the best squared distance seen so far.
4. For each command:
   • rotate if the command is -1 or -2
   • otherwise simulate one step at a time
5. Before taking a step, check whether the next cell is an obstacle.
6. If blocked, stop that command immediately.
7. If not blocked, move and update the answer with x * x + y * y.

Why This Works Well

The robot only needs to know one thing before every forward step:

Is the next cell blocked?

A hash set answers that quickly, and because every command is at most 9, the simulation stays efficient.

import java.util.HashSet;
import java.util.Set;

class Solution {
    private static final int HASH_MULTIPLIER = 60013;

    public int robotSim(int[] commands, int[][] obstacles) {
        Set<Integer> obstacleSet = new HashSet<>();
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0;
        int y = 0;
        int direction = 0;
        long maxDistance = 0;

        for (int[] obstacle : obstacles) {
            obstacleSet.add(hashCoordinates(obstacle[0], obstacle[1]));
        }

        for (int command : commands) {
            if (command == -1) {
                direction = (direction + 1) % 4;
            } else if (command == -2) {
                direction = (direction + 3) % 4;
            } else {
                for (int step = 0; step < command; step++) {
                    int nextX = x + directions[direction][0];
                    int nextY = y + directions[direction][1];

                    if (obstacleSet.contains(hashCoordinates(nextX, nextY))) {
                        break;
                    }

                    x = nextX;
                    y = nextY;
                    maxDistance = Math.max(maxDistance, 1L * x * x + 1L * y * y);
                }
            }
        }

        return (int) maxDistance;
    }

    private int hashCoordinates(int x, int y) {
        return x + HASH_MULTIPLIER * y;
    }
}

Dry Run

Take the classic example:

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

Start:

• position = (0, 0)
• direction = north
• max distance = 0

Command 4

Move north four times:

• (0, 1) -> distance 1
• (0, 2) -> distance 4
• (0, 3) -> distance 9
• (0, 4) -> distance 16

Command -1

Turn right. Now the robot faces east.

Command 4

Try moving east:

• (1, 4) is free, move there
• (2, 4) is an obstacle, stop immediately

So after this command, the robot stays at (1, 4). The best squared distance becomes 1 * 1 + 4 * 4 = 17.

Command -2

Turn left. Now the robot faces north again.

Command 4

Move north four steps:

• (1, 5) -> 26
• (1, 6) -> 37
• (1, 7) -> 50
• (1, 8) -> 65

Final answer: 65

Why The Hashing Trick Is Safe

We want different coordinates to map to different set keys.

If we use:

x + 60013 * y

then changing y shifts the value by a large enough amount that two legal coordinates cannot overlap with each other inside the problem's bounds.

That lets us treat a 2D point like a single hashable number.

Correctness Intuition

At every forward step, the algorithm checks exactly the next cell the robot would enter.

• If that cell contains an obstacle, the robot must stop there according to the problem statement.
• If it does not contain an obstacle, moving into it is valid.

Because we process commands in order and simulate every allowed step in order, the robot's position always matches the real journey.

Since we update the answer after every successful move, the stored maximum is exactly the farthest squared distance ever reached.

Complexity Analysis

Let:

• m = number of commands
• n = number of obstacles

Time Complexity: O(m + n)

• building the obstacle set takes O(n)
• each command is processed once
• a forward command takes at most 9 steps, which is still constant work

So the whole simulation is linear.

Space Complexity: O(n)

The obstacle hash set stores up to n blocked cells.

Common Mistakes

1. Tracking only the final distance

The robot may reach its farthest point in the middle of the walk. The answer is not necessarily the final position.

2. Moving k cells in one jump

A command like 6 must be processed step by step. Otherwise you can skip over an obstacle that should have stopped the robot earlier.

3. Checking obstacles with a linear scan

That makes each move expensive and can turn a simple simulation into a slow one.

4. Using an unsafe coordinate encoding

If the hash function is not unique for the allowed coordinate range, two different obstacles can collide into the same key and break the simulation.

Final Takeaway

This problem looks like pure simulation, but the real optimization is in how we represent obstacles.

Once obstacle lookup becomes constant-time, the rest of the solution is clean:

• track direction with an index
• move one step at a time
• update the best squared distance after each valid move

That combination gives a direct and efficient O(m + n) solution.

Related Problems

• Robot Return to Origin — Easy
• Robot Collisions — Hard
• Asteroid Collision — Medium