⚡Flashcard Drill➔
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

  1. Simulate the robot step by step, tracking its position and heading.
  2. Store the obstacles in a hash set so that each candidate cell can be tested in O(1).
  3. For a move command, advance one unit at a time; if the next cell holds an obstacle, stop the whole move and stay put.
  4. After every command, update the maximum of x^2 + y^2 seen 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 k units 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: -2 is a left turn and -1 is a right turn.
  • Forgetting to update best after 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems