NeetCode #921LC-874MediumMath & Geometry
← Back to All Problems#921 · #874 · Walking Robot Simulation(模拟行走机器人)
📌 Problem Statement & Constraints
A robot starts at
(0, 0) facing north on an infinite plane containing obstacles at the given coordinates. It executes commands in order: a positive integer k moves it forward k units (stopping immediately if the next cell is blocked), -2 turns left 90 degrees, and -1 turns right 90 degrees. Return the maximum squared Euclidean distance from the origin that the robot reaches. Constraints: 1 <= commands.length <= 10^4, 0 <= obstacles.length <= 10^4, -3 * 10^4 <= xi, yi <= 3 * 10^4, obstacles are unique and never at the origin.💡 Core Algorithmic Approaches
- Simulate the robot step by step, tracking its position and heading.
- Store the obstacles in a hash set so that each candidate cell can be tested in O(1).
- For a move command, advance one unit at a time; if the next cell holds an obstacle, stop the whole move and stay put.
- After every command, update the maximum of
x^2 + y^2seen so far.
💻 Benchmark Python3 Implementation
class Solution:
def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
obs = {(x, y) for x, y in obstacles}
# directions: north, east, south, west
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
x = y = 0
d = 0
best = 0
for c in commands:
if c == -2:
d = (d + 3) % 4 # turn left
elif c == -1:
d = (d + 1) % 4 # turn right
else:
dx, dy = dirs[d]
for _ in range(c):
nx, ny = x + dx, y + dy
if (nx, ny) in obs:
break # blocked: stay put, end this move
x, y = nx, ny
best = max(best, x * x + y * y)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(C + O): C is the total number of forward steps and O the number of obstacles; the hash set makes each step O(1).
💾 Space Complexity
O(O): the obstacle set.
⚠️ Interview Pitfalls & Follow-ups
- Jumping
kunits at once: an obstacle anywhere along the path blocks the robot, so the move must be simulated unit by unit. - Continuing after a collision: when blocked, the robot stays in place and the remainder of that command is discarded.
- Reversing the turn codes:
-2is a left turn and-1is a right turn. - Forgetting to update
bestafter a move: the maximum distance can occur at the end of any move command, so it must be updated there.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.