874. Walking Robot Simulation - Detailed Explanation

Problem Statement

You have a robot starting at (0, 0) on an infinite grid, initially facing north. You’re given an array commands of integers and a list of obstacle coordinates obstacles. For each command:

• If the command is -2, turn left 90°.
• If the command is -1, turn right 90°.
• If the command is a positive integer k, move forward k steps, one unit at a time. You stop early if the next cell is an obstacle.

Return the maximum Euclidean distance squared from the origin that the robot achieves at any point.

Examples

Input:

commands = [4, -1, 3]
obstacles = []

Output:

25

Explanation: Moves 4 north → (0,4), turns right to east, moves 3 → (3,4). Max distance² = 3²+4² = 25.

Input:

commands = [4, -1, 4, -2, 4]
obstacles = [[2,4]]

Output:

65

Explanation:

• Move 4 north → (0,4)
• Turn right, move 4 east but obstacle at (2,4) stops you at (1,4)
• Turn left, move 4 north → (1,8)
  Max distance² = 1²+8² = 65.

Input:

commands = [6, -1, -1, 6]
obstacles = []

Output:

36

Explanation: Move 6 north → (0,6), two right turns face south, move 6 back to (0,0). Max distance² was 36.

Constraints

• 1 ≤ commands.length ≤ 10⁴
• 0 ≤ obstacles.length ≤ 10⁴
• Coordinates and step counts fit in 32‑bit integers.

Hints

1. Store obstacles in a HashSet for O(1) lookup of blocked cells.
2. Represent direction as an index into a dx/dy array and update it on turns.
3. After each step, update max distance².

Approach 1 – Simulation with HashSet

Explanation

We simulate step by step. Keep a set of obstacle positions encoded as strings (or tuples). Track current position (x,y) and a direction index d in [(0,1),(1,0),(0,-1),(-1,0)] for N, E, S, W. For each command:

• If turn, adjust d = (d ± 1) mod 4.
• If move k, loop k times: compute (nx,ny) = (x + dx[d], y + dy[d]); if (nx,ny) is in the obstacle set, break; else update (x,y) and ans = max(ans, x*x + y*y).

Step-by-step Walkthrough

Starting at (0,0), facing North (d=0):

1. Command 4 → try 4 moves north: (0,1),(0,2),(0,3),(0,4); update max = 16.
2. Command -1 → turn right: d = 1 (East).
3. Command 3 → move east to (1,4),(2,4),(3,4); no obstacles → update max = 25.

Visual Example

Start → (0,0)↑
Move 4 → (0,4)
Turn right →
Move 3 → (3,4)

Python Implementation

Java Implementation

Complexity Analysis

• Time: O(C + O) where C = total steps across all commands (∑cmds) and O = number of obstacles. Each step does an O(1) hash lookup.
• Space: O(O) to store the obstacles in a set.

Common Mistakes

• Encoding obstacle coordinates improperly (use a unique key, e.g. tuple or bit‑packed long).
• Forgetting to update the max distance on every successful move.
• Mixing up turn directions (left vs. right modular arithmetic).

Edge Cases

• No obstacles at all.
• Obstacles surrounding the start so the robot never moves.
• Commands that never include movement (only turns).
• Very large step commands with no obstacles (ensure performance).

Alternative Variations

• Preprocessing obstacles by row/column into sorted lists and using binary search to jump directly to the next obstacle in a given direction, reducing per‑step loops.
• Allow diagonal moves or different turn angles.
• Count the number of distinct positions visited.

Related Problems

• Robot Room Cleaner

• Unique Paths