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.The key idea for #874 Walking Robot Simulation is to simulate the robot’s movement step by step while tracking its direction and avoiding obstacles. The robot can turn left or right and move forward based on a sequence of commands. Instead of recalculating directions each time, maintain a direction index with a predefined list of direction vectors such as (0,1), (1,0), (0,-1), (-1,0).
To efficiently detect obstacles, store their coordinates in a hash set. This allows O(1) lookup when checking whether the robot can move to the next cell. For each forward command, move one step at a time and stop if the next position is an obstacle. While moving, continuously track the maximum squared Euclidean distance x*x + y*y from the origin.
This approach relies on simulation with hashing, ensuring fast obstacle detection and efficient command processing without scanning the obstacle list repeatedly.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Simulation with Hash Set for Obstacles | O(C + S) | O(O) |
NeetCodeIO
Simulate the movement of the robot by maintaining a variable for the current direction. Use an array to store the possible directions: north, east, south, and west. When a turn command is received, adjust the direction index. For movement commands, move the robot in the direction indexed by the current direction.
Time Complexity: O(N + M), where N is the number of commands and M is the number of obstacles.
Space Complexity: O(M), where M is the number of obstacles.
1def robotSim(commands, obstacles):
2 obstacle_set = set(map(tuple, obstacles))
3 # Directions: north, east, south, west
4 dx = [0, 1, 0, -1]
5 dy = [1, 0, -1, 0]
6 x = y = 0
7 direction = 0
8 max_distance_sq = 0
9
10 for command in commands:
11 if command == -2: # Turn left
12 direction = (direction - 1) % 4
13 elif command == -1: # Turn right
14 direction = (direction + 1) % 4
15 else:
16 for _ in range(command):
17 if (x + dx[direction], y + dy[direction]) not in obstacle_set:
18 x += dx[direction]
19 y += dy[direction]
20 else:
21 break
22 max_distance_sq = max(max_distance_sq, x * x + y * y)
23
24 return max_distance_sqThe solution defines the possible directions the robot can face using two arrays dx and dy. The direction is managed using a variable that cycles through the indices on executing turn commands. By maintaining a set of obstacles, it ensures efficient checks when the robot moves. The maximum squared distance is updated whenever the robot's position changes.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, simulation and grid-based movement problems like Walking Robot Simulation are common in coding interviews. They test your ability to manage directions, handle edge cases, and use hash-based lookups efficiently.
A hash set is the best data structure for storing obstacle coordinates. It allows O(1) average-time checks to determine whether the robot’s next step is blocked, which keeps the simulation efficient.
The optimal approach is to simulate the robot's movement while storing obstacles in a hash set for constant-time lookup. By updating direction using a direction array and moving step by step, we efficiently avoid obstacles and track the maximum distance from the origin.
The problem asks for the maximum Euclidean distance from the origin, but using squared distance avoids the computational cost of square roots. Comparing x*x + y*y values is sufficient to determine the farthest point.