Problem Description

You have a robot that starts at position (0, 0) on an infinite XY-plane, initially facing north. The robot needs to execute a sequence of commands given as an array of integers.

The robot can receive three types of commands:

• -2: Turn left 90 degrees
• -1: Turn right 90 degrees
• 1 to 9: Move forward by that many units, one step at a time

The plane contains obstacles at certain positions given as an array obstacles, where each obstacles[i] = (xi, yi) represents an obstacle at that coordinate. When the robot tries to move into an obstacle, it stops at the position just before the obstacle and continues with the next command.

Your task is to find the maximum squared Euclidean distance from the origin that the robot reaches at any point during its journey. The squared Euclidean distance from origin (0, 0) to point (x, y) is calculated as x² + y².

Important details:

• The robot moves in the four cardinal directions: North (+Y), East (+X), South (-Y), and West (-X)
• If there's an obstacle at (0, 0), the robot ignores it initially but cannot return to the origin later
• When executing a forward movement command of k units, the robot moves one unit at a time and checks for obstacles at each step
• If an obstacle blocks the path, the robot stops and proceeds to the next command

For example, if the robot reaches a maximum distance of 5 units from the origin at some point, you should return 25 (which is 5²).

Intuition

The problem is essentially a simulation where we need to track the robot's position as it follows commands. The key insight is that we need to handle three distinct operations: turning left, turning right, and moving forward.

For handling directions, instead of using complex conditional logic or switch statements, we can use a clever trick with a direction array. If we represent the four cardinal directions as vectors: North (0, 1), East (1, 0), South (0, -1), and West (-1, 0), we notice these form a cycle. We can store these as a flattened array [0, 1, 0, -1, 0] where consecutive pairs represent each direction.

Why this representation? When we turn right, we move to the next direction in the cycle (incrementing our direction index by 1). When we turn left, we move three positions forward in the cycle (which is equivalent to moving one position backward). Using modulo 4 ensures we wrap around correctly.

For obstacle detection, we need to check if a position is blocked before moving there. Since we might need to check many positions (the robot can move up to 9 steps per command), and there could be many obstacles, using a hash set for obstacle coordinates gives us O(1) lookup time for each position check.

The crucial observation for forward movement is that we must move one unit at a time rather than jumping directly to the final position. This is because an obstacle might block our path midway, and we need to stop just before hitting it. Each step forward involves calculating the next position based on our current direction and checking if it's blocked.

Throughout the simulation, we track the maximum squared distance after each successful move. We calculate x² + y² at each new position and update our answer if this value is larger than what we've seen before. This ensures we capture the farthest point the robot reaches during its entire journey.

Solution Approach

The implementation follows a simulation approach with efficient data structures for direction management and obstacle detection.

Direction Management: We use a direction array dirs = [0, 1, 0, -1, 0] where consecutive pairs represent direction vectors:

• Index k=0: (dirs[0], dirs[1]) = (0, 1) represents North
• Index k=1: (dirs[1], dirs[2]) = (1, 0) represents East
• Index k=2: (dirs[2], dirs[3]) = (0, -1) represents South
• Index k=3: (dirs[3], dirs[4]) = (-1, 0) represents West

The variable k tracks our current direction index (0 to 3).

Obstacle Storage: We convert the obstacles list into a set s = {(x, y) for x, y in obstacles} for O(1) lookup time when checking if a position is blocked.

Command Processing: We iterate through each command c in the commands array:

1. Turn Left (c = -2):

   • Update direction: k = (k + 3) % 4
   • Adding 3 is equivalent to subtracting 1 in modulo 4, effectively rotating counterclockwise

2. Turn Right (c = -1):

   • Update direction: k = (k + 1) % 4
   • This rotates clockwise through our direction cycle

3. Move Forward (1 ≤ c ≤ 9):

   • For each of the c steps:
     • Calculate next position: nx = x + dirs[k], ny = y + dirs[k + 1]
     • Check if (nx, ny) is in obstacle set s
     • If blocked, break from the movement loop
     • If clear, update position: x, y = nx, ny
     • Update maximum distance: ans = max(ans, x² + y²)

Tracking Maximum Distance: After each successful move, we calculate the squared Euclidean distance x² + y² and update ans if this exceeds the previous maximum. This ensures we capture the farthest point reached throughout the entire journey.

The algorithm runs in O(M + N) time complexity, where M is the total number of steps taken (sum of all forward movement commands) and N is the number of obstacles (for set creation). The space complexity is O(N) for storing the obstacle set.

Example Walkthrough

Let's trace through a small example to illustrate the solution approach.

Input:

• commands = [4, -1, 3]
• obstacles = [(2, 4)]

Initial Setup:

• Robot starts at position (0, 0) facing North
• Direction array: dirs = [0, 1, 0, -1, 0]
• Current direction index: k = 0 (North)
• Obstacle set: s = {(2, 4)}
• Maximum distance: ans = 0

Step 1: Command 4 (move forward 4 units)

• Robot is facing North, so direction vector is (dirs[0], dirs[1]) = (0, 1)
• Move one unit at a time:
  • Step 1: Next position (0+0, 0+1) = (0, 1). Not blocked. Move to (0, 1). Distance = 0² + 1² = 1
  • Step 2: Next position (0+0, 1+1) = (0, 2). Not blocked. Move to (0, 2). Distance = 0² + 2² = 4
  • Step 3: Next position (0+0, 2+1) = (0, 3). Not blocked. Move to (0, 3). Distance = 0² + 3² = 9
  • Step 4: Next position (0+0, 3+1) = (0, 4). Not blocked. Move to (0, 4). Distance = 0² + 4² = 16
• Current position: (0, 4), ans = 16

Step 2: Command -1 (turn right)

• Update direction: k = (0 + 1) % 4 = 1
• Robot now faces East (dirs[1], dirs[2]) = (1, 0)
• Position remains (0, 4), ans = 16

Step 3: Command 3 (move forward 3 units)

• Robot is facing East, so direction vector is (1, 0)
• Move one unit at a time:
  • Step 1: Next position (0+1, 4+0) = (1, 4). Not blocked. Move to (1, 4). Distance = 1² + 4² = 17
  • Step 2: Next position (1+1, 4+0) = (2, 4). Blocked by obstacle! Stop here.
• Robot stops at (1, 4) and cannot complete the remaining movement
• Current position: (1, 4), ans = 17

Final Result: The maximum squared distance reached is 17 (at position (1, 4)).

This example demonstrates:

• How the robot moves one unit at a time
• How obstacles block movement mid-command
• How turning changes the direction index
• How we track the maximum distance throughout the journey

Solution Implementation

Time and Space Complexity

Time Complexity: O(C × n + m)

The time complexity consists of two main parts:

• Creating the obstacle set takes O(m) time, where m is the number of obstacles
• Processing commands takes O(C × n) time, where:
  • n is the number of commands in the commands array
  • C is the maximum distance value in a forward movement command (the maximum value of positive commands)
  • For each command, if it's a turn command (-1 or -2), it takes O(1) time
  • For each forward movement command with value c, the robot attempts to move up to c steps, checking for obstacles at each step, which takes O(c) time in the worst case
  • Since we could have up to C steps for any command, and we process n commands total, this gives us O(C × n)

Overall time complexity: O(C × n + m)

Space Complexity: O(m)

The space complexity is determined by:

• The obstacle set s which stores all m obstacles as tuples, requiring O(m) space
• Other variables (dirs, ans, k, x, y, nx, ny) use constant space O(1)

Overall space complexity: O(m)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Update Maximum Distance After Each Step

Pitfall: A common mistake is only checking the maximum distance after completing all commands or after each command, rather than after each individual step during forward movement.

# INCORRECT: Only updates after completing the entire movement command
for command in commands:
    if command > 0:
        for _ in range(command):
            next_x = current_x + directions[direction_index]
            next_y = current_y + directions[direction_index + 1]
            if (next_x, next_y) not in obstacle_set:
                current_x = next_x
                current_y = next_y
        # Wrong: Only checking distance after all steps
        max_distance_squared = max(max_distance_squared, 
                                  current_x * current_x + current_y * current_y)

Solution: Update the maximum distance after EACH successful step, not just after completing a command:

# CORRECT: Updates after each individual step
for _ in range(command):
    next_x = current_x + directions[direction_index]
    next_y = current_y + directions[direction_index + 1]
    if (next_x, next_y) in obstacle_set:
        break
    current_x = next_x
    current_y = next_y
    # Correct: Check distance after each step
    max_distance_squared = max(max_distance_squared, 
                              current_x * current_x + current_y * current_y)

2. Incorrect Handling of Obstacle Set Creation

Pitfall: Creating the obstacle set with incorrect tuple unpacking or data structure:

# INCORRECT: Creates set of lists (unhashable type error)
obstacle_set = {obstacle for obstacle in obstacles}

# INCORRECT: Creates set incorrectly if obstacles format varies
obstacle_set = set(obstacles)  # May fail if obstacles contains lists

Solution: Explicitly convert each obstacle to a tuple:

# CORRECT: Ensures each obstacle is a hashable tuple
obstacle_set = {(x, y) for x, y in obstacles}
# Or alternatively:
obstacle_set = {tuple(obstacle) for obstacle in obstacles}

3. Off-by-One Error in Direction Array Indexing

Pitfall: Using incorrect indexing when accessing direction vectors from the flattened array:

# INCORRECT: May cause index out of bounds
directions = [0, 1, 0, -1, 0]
next_x = current_x + directions[direction_index * 2]      # Wrong formula
next_y = current_y + directions[direction_index * 2 + 1]  # Wrong formula

Solution: Use the correct indexing pattern where consecutive elements form direction pairs:

# CORRECT: Proper indexing for flattened direction array
directions = (0, 1, 0, -1, 0)
next_x = current_x + directions[direction_index]      # Index k gives dx
next_y = current_y + directions[direction_index + 1]  # Index k+1 gives dy

4. Not Breaking Immediately When Obstacle is Encountered

Pitfall: Continuing to try moving after hitting an obstacle within the same command:

# INCORRECT: Doesn't stop when obstacle is hit
for _ in range(command):
    next_x = current_x + directions[direction_index]
    next_y = current_y + directions[direction_index + 1]
    if (next_x, next_y) not in obstacle_set:
        current_x = next_x
        current_y = next_y
    # Wrong: Continues looping even after hitting obstacle

Solution: Use break to stop the movement loop immediately upon encountering an obstacle:

# CORRECT: Stops immediately when obstacle is encountered
for _ in range(command):
    next_x = current_x + directions[direction_index]
    next_y = current_y + directions[direction_index + 1]
    if (next_x, next_y) in obstacle_set:
        break  # Stop trying to move further
    current_x = next_x
    current_y = next_y