Problem

A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot can receive a sequence of these three possible types of commands:

  • -2: Turn left 90 degrees.
  • -1: Turn right 90 degrees.
  • 1 <= k <= 9: Move forward k units, one unit at a time.

Some of the grid squares are obstacles. The ith obstacle is at grid point obstacles[i] = (xi, yi). If the robot runs into an obstacle, then it will instead stay in its current location and move on to the next command.

Return the maximum Euclidean distance that the robot ever gets from the origin squared (i.e. if the distance is 5, return 25).

Note:

  • North means +Y direction.
  • East means +X direction.
  • South means -Y direction.
  • West means -X direction.
  • There can be obstacle in [0,0].

Examples

Example 1:

1
2
3
4
5
6
7

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: The robot starts at (0, 0):
1. Move north 4 units to (0, 4).
2. Turn right.
3. Move east 3 units to (3, 4).
The furthest point the robot ever gets from the origin is (3, 4), which squared is 32 + 42 = 25 units away.

Example 2:

1
2
3
4
5
6
7
8
9

Input: commands = [4,-1,4,-2,4], obstacles =[[2,4]]
Output: 65
Explanation: The robot starts at (0, 0):
1. Move north 4 units to (0, 4).
2. Turn right.
3. Move east 1 unit and get blocked by the obstacle at (2, 4), robot is at (1, 4).
4. Turn left.
5. Move north 4 units to (1, 8).
The furthest point the robot ever gets from the origin is (1, 8), which squared is 12 + 82 = 65 units away.

Example 3:

1
2
3
4
5
6
7
8

Input: commands = [6,-1,-1,6], obstacles = []
Output: 36
Explanation: The robot starts at (0, 0):
1. Move north 6 units to (0, 6).
2. Turn right.
3. Turn right.
4. Move south 6 units to (0, 0).
The furthest point the robot ever gets from the origin is (0, 6), which squared is 62 = 36 units away.

Solution

Method 1 - Run the simulation

Here are the steps we can take:

  1. Track Directions using an array (North, East, South, West).
  2. Handle Commands to adjust the direction or move the robot.
  3. Use a Set to store obstacles for fast lookup.
  4. Calculate and Track the maximum Euclidean distance squared.

Video explanation

Here is the video explanation:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

public class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        // Convert obstacles list to a set of strings for faster lookup
        Set<String> obstacleSet = new HashSet<>();
        for (int[] obstacle : obstacles) {
            obstacleSet.add(obstacle[0] + "," + obstacle[1]);
        }
        
        // Directions are in the order of North, East, South, West
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIdx = 0; // Start facing north
        int x = 0, y = 0; // Robot's starting position
        int maxDistanceSq = 0;

        for (int command : commands) {
            if (command == -1) { // Turn right 90 degrees
                directionIdx = (directionIdx + 1) % 4;
            } else if (command == -2) { // Turn left 90 degrees
                directionIdx = (directionIdx + 3) % 4;
            } else { // Move forward k units
                int dx = directions[directionIdx][0];
                int dy = directions[directionIdx][1];
                
                int steps = 0;
                while (steps < command) {
                    int nextX = x + dx;
                    int nextY = y + dy;
                    // Check for obstacle
                    if (obstacleSet.contains(nextX + "," + nextY)) {
	                    break; // Hit an obstacle, stop moving forward
                    }
					x = nextX;
					y = nextY;
					// Calculate the current distance squared and update
					// maxDistanceSq
					maxDistanceSq = Math.max(maxDistanceSq, x * x + y * y);                    
                    steps++;
                }
            }
        }

        return maxDistanceSq;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        # Convert obstacles list to a set of tuples for faster lookup
        obstacle_set = set(map(tuple, obstacles))

        # Directions are in the order of North, East, South, West
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        direction_idx = 0  # Start facing north
        x, y = 0, 0  # Robot's starting position
        max_distance_sq = 0

        for command in commands:
            if command == -1:  # Turn right 90 degrees
                direction_idx = (direction_idx + 1) % 4
            elif command == -2:  # Turn left 90 degrees
                direction_idx = (direction_idx + 3) % 4
            else:  # Move forward k units
                dx, dy = directions[direction_idx]

                steps = 0
                while steps < command:
                    next_x = x + dx
                    next_y = y + dy
                    # Check for obstacle
                    if (next_x, next_y) in obstacle_set:
                        break  # Hit an obstacle, stop moving forward

                    x, y = next_x, next_y
                    # Calculate the current distance squared and update max_distance_sq
                    max_distance_sq = max(max_distance_sq, x * x + y * y)
                    steps += 1

        return max_distance_sq

Complexity

  • ⏰ Time complexity: O(o + c) where o is number of obstacles and c is number of commands.
    • Creating obstacle set takes O(o) time
    • Processing all commands takes O(c) time
  • 🧺 Space complexity: O(o) for storing obstacles.