Practice/Meta/Leetcode 874. Walking Robot Simulation

Leetcode 874. Walking Robot Simulation

CodingMust

Problem

You are simulating a robot moving on an infinite 2D grid. The robot starts at the origin point (0, 0) facing north (positive Y direction).

The robot receives a sequence of commands:

• A positive integer k means move forward k units in the current direction
• -1 means turn right 90 degrees
• -2 means turn left 90 degrees

The grid also contains obstacles at specific coordinates. When executing a forward movement command, the robot moves one unit at a time. If the next step would place the robot on an obstacle, the robot stops moving for that command (but retains its direction) and proceeds to the next command.

Your task is to simulate the robot's movement and return the maximum squared Euclidean distance from the origin that the robot reaches at any point during its journey.

The squared Euclidean distance for a point (x, y) is calculated as x² + y².

Requirements

1. Process each command sequentially in the order given
2. For movement commands, advance one unit at a time (not all at once)
3. Stop immediately if the next unit step would collide with an obstacle
4. Track the maximum squared distance from origin throughout the entire path
5. Use an efficient data structure for obstacle lookup (O(1) average case)

Constraints

• 1 ≤ commands.length ≤ 10⁴
• commands[i] is either -2, -1, or an integer in the range [1, 9]
• 0 ≤ obstacles.length ≤ 10⁴
• -3 × 10⁴ ≤ obstacles[i][0], obstacles[i][1] ≤ 3 × 10⁴
• The robot will never start on an obstacle
• All obstacle coordinates are unique

Examples

Example 1:

` Input: commands = [4, -1, 3], obstacles = [] Output: 25 Explanation:

• Robot starts at (0, 0) facing north
• Move 4 units north to (0, 4)
• Turn right to face east
• Move 3 units east to (3, 4)
• Maximum squared distance: 3² + 4² = 25 `

Example 2:

` Input: commands = [4, -1, 4, -2, 4], obstacles = [[2, 4]] Output: 65 Explanation:

• Robot moves north to (0, 4)
• Turns right to face east
• Attempts to move 4 units east but stops at (1, 4) due to obstacle at (2, 4)
• Turns left to face north again
• Moves 4 units north to (1, 8)
• Maximum squared distance: 1² + 8² = 65 `

Example 3:

Input: commands = [-1, -1, -2, -2], obstacles = [] Output: 0 Explanation: Robot only turns and never moves from origin.