LeetCode Problem 874

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Simulation

Solution

Problem Understanding

The problem describes a robot moving on an infinite two dimensional grid. The robot begins at coordinate (0, 0) and initially faces north, which corresponds to the positive Y direction. The robot processes a sequence of commands, where each command either changes its direction or moves it forward.

There are three kinds of commands:

• -2 means rotate left by 90 degrees.
• -1 means rotate right by 90 degrees.
• Any integer between 1 and 9 means move forward that many steps.

The important detail is that movement happens one unit at a time. This matters because obstacles may block the robot before it completes the entire forward movement. If the next square contains an obstacle, the robot immediately stops moving for that command and proceeds to the next command.

The input consists of two arrays:

• commands, which defines the sequence of robot instructions.
• obstacles, which contains blocked coordinates that the robot cannot enter.

The goal is not to compute the final position. Instead, we must track the maximum squared Euclidean distance from the origin that the robot reaches at any moment during its movement.

The squared Euclidean distance for a point (x, y) is:

$d = x^2 + y^2$

The problem asks for the maximum value of this expression encountered during the simulation.

The constraints are important because they guide the algorithm design:

• commands.length <= 10^4
• obstacles.length <= 10^4
• Coordinates range from -30000 to 30000

A naive obstacle lookup using linear search would be too slow because each movement step could require scanning all obstacles. Since the robot may process up to 9 * 10^4 individual movement steps, obstacle lookup must be efficient.

Several edge cases are important:

• Obstacles may include (0, 0). The robot starts there anyway, but cannot later move back onto the origin.
• Multiple turns may occur consecutively without movement.
• The robot may encounter an obstacle immediately adjacent to its current position.
• Coordinates may become negative as the robot moves south or west.
• The maximum distance may occur during intermediate movement, not necessarily at the final position.

Approaches

Brute Force Approach

The most direct solution is to simulate the robot exactly as described. For every movement command, we move one step at a time and check whether the next position is an obstacle.

The naive implementation problem comes from obstacle lookup. If obstacles are stored in a list, checking whether a coordinate is blocked requires scanning the entire obstacle array every time the robot moves one unit.

Suppose there are:

• C commands
• O obstacles
• Up to 9C total movement steps

Then every step may require O work, producing a total complexity of roughly O(C * O).

Since both arrays may contain 10^4 elements, this can become far too slow.

The brute force idea is still logically correct because it precisely follows the robot's movement rules, but the obstacle lookup mechanism is inefficient.

Optimal Approach

The key optimization is to store obstacles in a hash set instead of a list.

A hash set allows average O(1) obstacle lookup. This transforms the expensive repeated obstacle scans into constant time membership checks.

The robot still moves one step at a time because obstacle collisions must be detected precisely, but each step becomes efficient.

We also represent direction using an index into a direction array:

• North: (0, 1)
• East: (1, 0)
• South: (0, -1)
• West: (-1, 0)

Turning left or right simply updates the direction index modulo 4.

This approach efficiently simulates the robot while supporting fast obstacle detection.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(C * O)	O(O)	Linear obstacle lookup for every step
Optimal	O(C + O)	O(O)	Uses hash set for constant time obstacle checks

Algorithm Walkthrough

1. Create a hash set containing all obstacle coordinates.

We convert each obstacle coordinate into a tuple and store it in a set. This allows fast membership checks when determining whether the robot can move into a square. 2. Initialize the robot state.

The robot starts at:

• Position (0, 0)
• Facing north

We also initialize:

• max_distance = 0
• Direction index direction = 0

3. Define the direction vectors.

We store directions in clockwise order:

directions = [
    (0, 1),   # North
    (1, 0),   # East
    (0, -1),  # South
    (-1, 0)   # West
]

The direction index determines the robot's current orientation. 4. Process each command sequentially.

For every command:

• If command is -1, rotate right:

direction = (direction + 1) % 4

• If command is -2, rotate left:

direction = (direction - 1) % 4

• Otherwise, the command represents forward movement.

5. Move one step at a time for forward commands.

If the command value is k, repeat k times:

• Compute the next coordinate.
• Check whether it exists in the obstacle set.
• If blocked, stop processing this command immediately.
• Otherwise, update the robot position.

6. Update the maximum squared distance.

After every successful movement step, compute:

$x^2 + y^2$$h$$k$$r$$(x)^2 + (y)^2 = 3.0^2$Sliders update the center and radius of the circle equation.-10-8-6-4-2246810-6-4-2246

Compare it against the current maximum.

1. Return the maximum distance after all commands finish.

Why it works

The algorithm exactly simulates the robot according to the problem rules. Each forward command is processed one unit at a time, which guarantees obstacle collisions are handled correctly. Because the robot's state always reflects its true position and orientation after every instruction, the computed maximum distance is accurate. Using a hash set does not change the simulation behavior, it only improves obstacle lookup efficiency.

Python Solution

from typing import List

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

        directions = [
            (0, 1),   # North
            (1, 0),   # East
            (0, -1),  # South
            (-1, 0)   # West
        ]

        x = 0
        y = 0
        direction = 0
        max_distance = 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

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

        return max_distance

The implementation begins by converting all obstacles into a hash set. Python tuples are hashable, which makes coordinate storage straightforward and efficient.

The directions array encodes movement vectors in clockwise order. The variable direction stores the current orientation index. Rotations are handled using modular arithmetic, which avoids long conditional logic.

For movement commands, the algorithm advances the robot one unit at a time. This is critical because obstacles may interrupt movement before all requested steps are completed.

Each successful step updates the robot coordinates and recalculates the squared distance from the origin. The maximum value seen throughout the simulation is preserved in max_distance.

Finally, the function returns the maximum squared distance reached during the robot's path.

Go Solution

func robotSim(commands []int, obstacles [][]int) int {
	obstacleSet := make(map[[2]int]bool)

	for _, obstacle := range obstacles {
		obstacleSet[[2]int{obstacle[0], obstacle[1]}] = true
	}

	directions := [][2]int{
		{0, 1},  // North
		{1, 0},  // East
		{0, -1}, // South
		{-1, 0}, // West
	}

	x, y := 0, 0
	direction := 0
	maxDistance := 0

	for _, command := range commands {
		if command == -1 {
			direction = (direction + 1) % 4

		} else if command == -2 {
			direction = (direction + 3) % 4

		} else {
			dx := directions[direction][0]
			dy := directions[direction][1]

			for step := 0; step < command; step++ {
				nextX := x + dx
				nextY := y + dy

				if obstacleSet[[2]int{nextX, nextY}] {
					break
				}

				x = nextX
				y = nextY

				distance := x*x + y*y
				if distance > maxDistance {
					maxDistance = distance
				}
			}
		}
	}

	return maxDistance
}

The Go implementation follows the same algorithmic structure as the Python solution. Since Go does not support tuple keys directly, obstacle coordinates are stored using fixed size arrays of type [2]int.

Go modular arithmetic behaves differently for negative numbers, so left rotation uses:

(direction + 3) % 4

instead of subtracting 1 directly.

All integer operations safely fit within Go's standard int type because the problem guarantees the result remains below 2^31.

Worked Examples

Example 1

Input:

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

Initial state:

Variable	Value
Position	(0, 0)
Direction	North
Max Distance	0

Command = 4

Move north 4 steps.

Step	Position	Distance
1	(0, 1)	1
2	(0, 2)	4
3	(0, 3)	9
4	(0, 4)	16

Maximum distance becomes 16.

Command = -1

Turn right.

Direction changes from North to East.

Command = 3

Move east 3 steps.

Step	Position	Distance
1	(1, 4)	17
2	(2, 4)	20
3	(3, 4)	25

Final answer: 25

Example 2

Input:

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

Obstacle set:

{(2, 4)}

Command = 4

Robot moves north to (0, 4).

Maximum distance becomes 16.

Command = -1

Turn right, now facing east.

Command = 4

Attempt to move east.

Attempted Position	Obstacle?	Result
(1, 4)	No	Move succeeds
(2, 4)	Yes	Stop movement

Robot remains at (1, 4).

Distance:

$1^2 + 4^2 = 17$

Command = -2

Turn left, now facing north.

Command = 4

Move north.

Step	Position	Distance
1	(1, 5)	26
2	(1, 6)	37
3	(1, 7)	50
4	(1, 8)	65

Final answer: 65

Example 3

Input:

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

Obstacle set:

{(0, 0)}

Command = 6

Move north to (0, 6).

Maximum distance becomes 36.

Command = -1

Turn right, facing east.

Command = -1

Turn right again, facing south.

Command = 6

Move south.

Attempted Position	Allowed?
(0, 5)	Yes
(0, 4)	Yes
(0, 3)	Yes
(0, 2)	Yes
(0, 1)	Yes
(0, 0)	Blocked

Robot stops at (0, 1).

Maximum distance remains 36.

Final answer: 36

Complexity Analysis

Measure	Complexity	Explanation
Time	O(C + O)	Building the obstacle set costs O(O), simulation processes each command and movement step once
Space	O(O)	The obstacle hash set stores all obstacle coordinates

The robot moves at most 9 steps per movement command because command values are bounded by 9. Therefore, the total number of movement operations is proportional to the number of commands. Since hash set lookups are average O(1), the simulation remains efficient even with many obstacles.

Test Cases

from typing import List

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

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

        x = 0
        y = 0
        direction = 0
        max_distance = 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

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

        return max_distance

solution = Solution()

assert solution.robotSim([4, -1, 3], []) == 25
# Basic movement without obstacles

assert solution.robotSim([4, -1, 4, -2, 4], [[2, 4]]) == 65
# Obstacle blocks movement mid-command

assert solution.robotSim([6, -1, -1, 6], [[0, 0]]) == 36
# Obstacle at origin prevents return

assert solution.robotSim([], []) == 0
# No commands

assert solution.robotSim([1, 1, 1, 1], []) == 16
# Straight north movement

assert solution.robotSim([-1, -1, -1, -1], []) == 0
# Rotations only

assert solution.robotSim([9], [[0, 1]]) == 0
# Immediate obstacle blocks movement

assert solution.robotSim([9], []) == 81
# Maximum single command distance

assert solution.robotSim([2, -1, 2, -1, 2, -1, 2], []) == 8
# Square path returns near origin

assert solution.robotSim([3, -2, 3, -2, 3, -2, 3], []) == 18
# Multiple left turns

assert solution.robotSim([1, -1, 1, -1, 1, -1, 1], []) == 2
# Full rotation cycle

assert solution.robotSim([4, -1, 4], [[4, 4]])
# Obstacle not encountered

Test	Why
[4, -1, 3]	Basic movement and turning
[4, -1, 4, -2, 4] with obstacle	Tests obstacle interruption
Obstacle at (0,0)	Validates special origin behavior
Empty commands	Tests minimal input
Straight north movement	Simple accumulation case
Rotations only	Ensures turning logic works
Immediate obstacle	Tests blocked movement from current position
Single large move	Tests maximum movement command
Square movement path	Ensures directional cycling correctness
Multiple left turns	Validates modulo direction updates
Full rotation cycle	Confirms orientation resets correctly
Unreached obstacle	Ensures irrelevant obstacles do not affect movement

Edge Cases

One important edge case occurs when an obstacle is immediately adjacent to the robot. For example, if the robot faces north and (0, 1) is blocked, a forward movement command should result in no movement at all. A buggy implementation that updates the position before checking obstacles would incorrectly allow the robot to enter the blocked square. This solution avoids that issue by always checking the next position before updating coordinates.

Another tricky case involves an obstacle at the origin (0, 0). The problem explicitly states that the robot ignores this obstacle initially because it starts there. However, after leaving the origin, it cannot move back onto it. Some implementations mistakenly treat the starting square as blocked immediately. This algorithm naturally handles the rule correctly because obstacle checks only occur for future movement positions.

Direction handling is another common source of bugs. Consecutive left and right turns can easily produce incorrect orientation if modular arithmetic is mishandled. For example, turning left from north should wrap around to west. Using a direction array with modulo arithmetic guarantees correct cyclic rotation behavior.

A final subtle edge case occurs when the maximum distance is reached during movement rather than at the final position. The robot may later move closer to the origin. If the implementation only checks the final coordinate, it will produce incorrect results. This solution updates the maximum distance after every successful step, ensuring all intermediate positions are considered correctly.