Watch 10 video solutions for Walking Robot Simulation, a medium level problem involving Array, Hash Table, Simulation. This walkthrough by NeetCodeIO has 12,313 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot receives an array of integers commands, which represents a sequence of moves that it needs to execute. There are only three possible types of instructions the robot can receive:
-2: Turn left 90 degrees.-1: Turn right 90 degrees.1 <= k <= 9: Move forward k units, one unit at a time.Some of the grid squares are obstacles. The ith obstacle is at grid point obstacles[i] = (xi, yi). If the robot runs into an obstacle, it will stay in its current location (on the block adjacent to the obstacle) and move onto the next command.
Return the maximum squared Euclidean distance that the robot reaches at any point in its path (i.e. if the distance is 5, return 25).
Note:
(0, 0). If this happens, the robot will ignore the obstacle until it has moved off the origin. However, it will be unable to return to (0, 0) due to the obstacle.
Example 1:
Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation:
The robot starts at (0, 0):
(0, 4).(3, 4).The furthest point the robot ever gets from the origin is (3, 4), which squared is 32 + 42 = 25 units away.
Example 2:
Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation:
The robot starts at (0, 0):
(0, 4).(2, 4), robot is at (1, 4).(1, 8).The furthest point the robot ever gets from the origin is (1, 8), which squared is 12 + 82 = 65 units away.
Example 3:
Input: commands = [6,-1,-1,6], obstacles = [[0,0]]
Output: 36
Explanation:
The robot starts at (0, 0):
(0, 6).(0,0), robot is at (0, 1).The furthest point the robot ever gets from the origin is (0, 6), which squared is 62 = 36 units away.
Constraints:
1 <= commands.length <= 104commands[i] is either -2, -1, or an integer in the range [1, 9].0 <= obstacles.length <= 104-3 * 104 <= xi, yi <= 3 * 104231.Problem Overview: You control a robot on an infinite 2D grid starting at (0,0) facing north. The robot receives commands to move forward or rotate left/right. Some grid cells contain obstacles that block movement. The task is to simulate the robot’s path and return the maximum Euclidean distance squared from the origin reached during the simulation.
Approach 1: Naive Simulation with Obstacle Scan (O(n * k) time, O(1) space)
The straightforward solution simulates each command step-by-step. For every forward movement, the robot advances one unit at a time while checking if the next coordinate matches any obstacle. If obstacles are stored in a list, every step requires scanning the entire list to determine whether movement is blocked. With k obstacles and up to n movement steps, this results in O(n * k) time complexity. The logic is simple and demonstrates how robot movement works, but obstacle lookup becomes the bottleneck as the number of obstacles grows.
Approach 2: Simulate Robot Movement Using Direction Array + Hash Set (O(n) time, O(k) space)
The optimal solution still performs step-by-step simulation but removes the expensive obstacle scan. Store all obstacle coordinates in a hash set so membership checks run in O(1) average time. Maintain a direction array such as [(0,1),(1,0),(0,-1),(-1,0)] representing north, east, south, and west. Rotation commands simply update a direction index using modulo arithmetic, while forward commands iterate step-by-step and check the next coordinate in the set. If the coordinate exists in the set, movement stops for that command. Otherwise update the robot’s position and track the maximum distance squared from the origin.
This approach relies heavily on constant-time lookups from a Hash Table and simple coordinate updates using an Array of direction vectors. The problem becomes a clean Simulation task where each step performs only a few arithmetic operations and one hash lookup.
Recommended for interviews: Interviewers expect the hash set + direction array approach. The naive scan demonstrates understanding of the robot simulation, but the optimized version shows you recognize the need for constant-time obstacle checks. Using a direction array keeps the code concise and avoids repeated conditional logic for turns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Simulation with Obstacle Scan | O(n * k) | O(1) | When obstacle count is very small or during initial brute-force reasoning |
| Direction Array + Hash Set Simulation | O(n) | O(k) | General case. Fast obstacle lookup and clean movement simulation |