874. Walking Robot Simulation

MediumArraySimulation

Problem Description

The problem describes a simulation where a robot navigates on an infinite two-dimensional grid starting from the origin point (0, 0) and facing north. The robot can process a series of commands:

-2: this command instructs the robot to turn 90 degrees to its left.
-1: this command instructs the robot to turn 90 degrees to its right.
1 <= k <= 9: move the robot k units forward in the direction it's currently facing.

There may also be obstacles on the grid at various points that prevent the robot's movement. An obstacle is defined by its coordinates on the grid. When given a command to move, if the robot encounters an obstacle, it will not move and proceed to the next command.

The goal is to calculate the maximum squared Euclidean distance from the origin that the robot ever reaches during the simulation. The Euclidean distance measures the straight-line distance between two points, and in this problem, it's squared to avoid dealing with square roots.

Intuition

The intuition behind the solution is to simulate the movement of the robot on the grid step by step, while keeping track of the maximum squared distance from the origin it has achieved. To represent the four cardinal directions (north, east, south, and west), we use a dirs array. This array contains deltas, or changes in the x and y coordinates, corresponding to the four possible directions. The robot's direction can then be effectively accessed by keeping an index k into this array. The index is updated whenever the robot receives a turn command.

Along with simulating the robot turn directions, the solution must also take into account the obstacles. This is done using a set s to store the grid coordinates of all obstacles, allowing the robot to check whether its next move would result in a collision—in such a case, the robot's movement is halted for the current command.

Simulating each command involves checking the type of command and updating the robot's state accordingly — turning or moving forward. The key is to perform each forward movement step-by-step to check for potential collisions with obstacles at every single step instead of leaping the full commanded distance at once.

By keeping track of the current coordinates of the robot and updating the maximum distance (squared) when the robot moves to a new position, the algorithm ensures that the maximum value is always available. That way, when all commands have been processed, the maximum squared distance (which is our main concern) can be returned as the solution.

Solution Approach

The solution employs a hash table and simple simulation to track the robot's movements and handle obstacles efficiently. Here's a breakdown of how it is implemented:

Direction Array: The dirs array ([0, 1, 0, -1, 0]) is cleverly designed so that pairs of adjacent elements correspond to directional vectors. Index k in this array corresponds to the current facing direction: (dirs[k], dirs[k + 1]). For instance, when k = 0, the direction is north ((0, 1)), and when k = 1, the direction is east ((1, 0)).
Obstacle Set: A set s stores the coordinates of all obstacles. Rather than a list, a set is used for its O(1) average lookup time, which is critical for performance as the robot needs to quickly check for obstacles at each step.
Variables for State: The x and y variables denote the current coordinates of the robot, whereas k represents the current facing direction. The ans variable keeps track of the maximum distance squared that the robot has been from the origin.
Command Processing:
- Turning: When a turn command -2 (turn left) or -1 (turn right) is encountered, the direction index k is updated modulo 4 to ensure it wraps around the dirs array correctly. Turning left (-2) results in k being incremented by 3 (equivalent to a 90-degree turn left), and modulo 4 ensures k stays within bounds. Turning right (-1) increments k by 1.
- Moving Forward: On a forward move command denoted by a positive integer c, the robot moves one step at a time for c steps. For each step, temporary new coordinates nx and ny are calculated using the current direction k. The robot checks whether these new coordinates collide with an obstacle by checking the set s. If there is a collision, the move is aborted, and the next command is processed. Otherwise, the robot's position is updated, and the ans variable is updated with the squared distance from the origin if it's larger than the previous value.

The solution simulates the robot's movements exactly as specified, carefully considering obstacles, and calculates the maximum squared distance from the origin efficiently.

Finally, the solution returns the ans variable, which holds the maximum squared distance from the origin the robot has achieved during its journey.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Assume the following inputs:

Commands: [4, -1, 4, -2, 4] Obstacles: [(2, 4)]

Now let's simulate the robot's behavior step by step:

The robot starts at the origin (0, 0) facing north. The maximum distance squared (ans) is currently 0.
The first command is 4. The robot moves forward 4 units to (0, 4). No obstacles are encountered. The distance squared is now 0^2 + 4^2 = 16, so ans is updated to 16.
The next command is -1, a turn to the right. The robot now faces east but hasn't moved yet, so ans remains 16.
The robot receives another 4 command to move forward. It will attempt to move from (0, 4) to (4, 4), but there is an obstacle at (2, 4). The robot stops before hitting the obstacle and remains at (2, 4). The distance squared is 2^2 + 4^2 = 20, so ans is updated to 20.
The robot is given a -2 command, which means turn left. Now it faces north again.
The last command is 4, so the robot attempts to move four units north. However, since it is already at (2, 4), it hits an obstacle immediately and does not move.

After processing all commands, the maximum distance squared the robot was from the origin is 20. This is the final ans returned by our simulation.

Throughout the process, the robot kept checking for obstacles and updating its position and maximum distance accordingly, while the turns were managed efficiently by using the dirs array and updating the index k. This example successfully illustrates how the provided solution approach rightly calculates the maximum squared distance using the commands and obstacles given.

Solution Implementation

1class Solution:
2    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
3        # Directions represent the movement of the robot: North, East, South, West
4        directions = (0, 1, 0, -1, 0)
5        # Set of obstacle positions for quick look-up
6        obstacle_set = {(x, y) for x, y in obstacles}
7        # Initialize the maximum distance squared, direction index, and starting position
8        max_distance_squared = direction_index = 0
9        position_x = position_y = 0
10
11        # Loop through each command and execute
12        for command in commands:
13            if command == -2:  # Turn left
14                direction_index = (direction_index + 3) % 4
15            elif command == -1: # Turn right
16                direction_index = (direction_index + 1) % 4
17            else:
18                # Move the robot forward for the number of steps specified in the command
19                for _ in range(command):
20                    next_x, next_y = position_x + directions[direction_index], position_y + directions[direction_index + 1]
21                    # Check if the new position is an obstacle
22                    if (next_x, next_y) in obstacle_set:
23                        break  # Stop if there's an obstacle ahead
24                    # Update the robot's position
25                    position_x, position_y = next_x, next_y
26                    # Update the maximum Euclidean distance squared from the origin
27                    max_distance_squared = max(max_distance_squared, position_x * position_x + position_y * position_y)
28      
29        # Return the maximum Euclidean distance squared the robot has been from the origin
30        return max_distance_squared
31

1class Solution {
2    public int robotSim(int[] commands, int[][] obstacles) {
3        // Directions for moving on the grid: North, East, South, West
4        int[] directionDeltas = {0, 1, 0, -1, 0};
5        // Set to store obstacle coordinates in encoded form
6        Set<Integer> obstacleSet = new HashSet<>(obstacles.length);
7        // Encode and add obstacles to the set
8        for (int[] obstacle : obstacles) {
9            obstacleSet.add(encodePosition(obstacle[0], obstacle[1]));
10        }
11        int maxDistanceSquared = 0; // Will hold the maximum squared distance from the origin
12        int directionIndex = 0; // Direction index points to the current direction
13        int x = 0, y = 0; // Robot's starting position at the origin (0, 0)
14        // Process each command to move the robot
15        for (int command : commands) {
16            if (command == -2) { // Turn left
17                directionIndex = (directionIndex + 3) % 4;
18            } else if (command == -1) { // Turn right
19                directionIndex = (directionIndex + 1) % 4;
20            } else {
21                // Move the robot forward by the number of steps specified by command
22                while (command-- > 0) {
23                    int nextX = x + directionDeltas[directionIndex];
24                    int nextY = y + directionDeltas[directionIndex + 1];
25                    // Check if the next position is an obstacle
26                    if (obstacleSet.contains(encodePosition(nextX, nextY))) {
27                        break; // Stop moving if an obstacle is encountered
28                    }
29                    // Update the robot's position
30                    x = nextX;
31                    y = nextY;
32                    // Calculate the squared distance from the origin and update maximum if necessary
33                    maxDistanceSquared = Math.max(maxDistanceSquared, x * x + y * y);
34                }
35            }
36        }
37        return maxDistanceSquared; // Return the maximum squared distance from the origin
38    }
39
40    // Helper method to encode a 2D grid position into a single integer.
41    // This is a common trick to store pairs as keys in a HashSet or HashMap.
42    // Here, we make the assumption that -30000 <= x,y <= 30000.
43    private int encodePosition(int x, int y) {
44        return x * 60010 + y;
45    }
46}
47

1#include <vector>
2#include <unordered_set>
3#include <algorithm>
4
5class Solution {
6public:
7    // This method simulates the movement of a robot according to given commands and obstacles.
8    // Returns the maximum squared Euclidean distance from the origin a robot reaches.
9    int robotSim(std::vector<int>& commands, std::vector<std::vector<int>>& obstacles) {
10        // Direction vectors for north, east, south, west.
11        int directions[5] = {0, 1, 0, -1, 0}; // last '0' is to allow easy access to 'y' direction with directions[k+1]
12
13        // Function to encode a pair of coordinates into a single integer.
14        auto hashFunction = [](int x, int y) {
15            return x * 60010 + y;
16        };
17      
18        // Set to hold the hashed locations of the obstacles.
19        std::unordered_set<int> obstacleSet;
20        for (const auto& obstacle : obstacles) {
21            obstacleSet.insert(hashFunction(obstacle[0], obstacle[1]));
22        }
23      
24        // Initialize variables to track the maximum Euclidean distance squared
25        // and the current direction index and coordinates of the robot.
26        int maxDistanceSquared = 0, directionIndex = 0;
27        int x = 0, y = 0; // Robot starts at the origin (0,0)
28
29        // Iterate through each command to move the robot.
30        for (int command : commands) {
31            if (command == -2) { // -2 means turn left 90 degrees
32                directionIndex = (directionIndex + 3) % 4; // rotate left in the directions array
33            } else if (command == -1) { // -1 means turn right 90 degrees
34                directionIndex = (directionIndex + 1) % 4; // rotate right in the directions array
35            } else {
36                // Move forward by 'command' steps.
37                while (command--) { // Loop over each step.
38                    // Calculate the next x and y after moving a step in the current direction.
39                    int nextX = x + directions[directionIndex];
40                    int nextY = y + directions[directionIndex + 1];
41
42                    // Check if next position is an obstacle.
43                    if (obstacleSet.count(hashFunction(nextX, nextY))) {
44                        break; // An obstacle blocks further movement in this direction.
45                    }
46
47                    // Update the robot's current position.
48                    x = nextX;
49                    y = nextY;
50
51                    // Update the max distance squared if necessary.
52                    maxDistanceSquared = std::max(maxDistanceSquared, x * x + y * y);
53                }
54            }
55        }
56      
57        // Return the maximum Euclidean distance squared that the robot has been from the origin.
58        return maxDistanceSquared;
59    }
60};
61

1function robotSim(commands: number[], obstacles: number[][]): number {
2    // Directions array defines the delta changes for north, east, south, west.
3    const directions = [0, 1, 0, -1, 0];
4  
5    // A Set to store the obstacles in a stringified form for quick look-up.
6    const obstacleSet: Set<number> = new Set();
7  
8    // Helper function to encode an obstacle's x and y coordinate into a single number.
9    const encodePosition = (x: number, y: number) => x * 60010 + y;
10  
11    // Add all obstacles to the Set using the encoding function.
12    for (const [obstacleX, obstacleY] of obstacles) {
13        obstacleSet.add(encodePosition(obstacleX, obstacleY));
14    }
15
16    // Initialize variables.
17    // 'maxDistanceSquared' holds the maximum squared distance from the origin.
18    // 'x' and 'y' represent the robot's current position.
19    // 'directionIndex' represents the current direction index.
20    let maxDistanceSquared = 0, x = 0, y = 0, directionIndex = 0;
21
22    // Iterate over the commands.
23    for (let command of commands) {
24        if (command === -2) {
25            // Turn left.
26            directionIndex = (directionIndex + 3) % 4;
27        } else if (command === -1) {
28            // Turn right.
29            directionIndex = (directionIndex + 1) % 4;
30        } else {
31            // Move forward 'command' steps.
32            while (command-- > 0) {
33                // Calculate the next position.
34                const nextX = x + directions[directionIndex];
35                const nextY = y + directions[directionIndex + 1];
36
37                // Check if the next position is an obstacle.
38                if (obstacleSet.has(encodePosition(nextX, nextY))) {
39                    break; // Stop moving if next position is an obstacle.
40                }
41
42                // Update the current position.
43                x = nextX;
44                y = nextY;
45
46                // Calculate and update the maximum squared distance from the origin.
47                maxDistanceSquared = Math.max(maxDistanceSquared, x * x + y * y);
48            }
49        }
50    }
51    // Return the maximum distance squared from the origin the robot can be.
52    return maxDistanceSquared;
53}
54

Time and Space Complexity

Time Complexity

The time complexity of the given code consists of iterating through each command and potentially iterating up to C times for each move command, where C is the max steps taken in any one move command.

Each turn command (-2 or -1) can be executed in constant time, O(1). For each move command, we iterate up to c times, and since we have n commands, the max number of steps (C) could be performed potentially n times, leading to a O(C * n).

Additionally, we check if the new position after each move is an obstacle; since we are using a set to contain obstacles and sets provide O(1) average time complexity for lookups, this does not significantly affect the overall time complexity per step.

Thus, the overall time complexity is O(C * n + m) where n is the total number of commands, and m is the total number of obstacles.

Space Complexity

The space complexity is determined by the storage used for the obstacle set and the few variables allocated for direction and position keeping, which are constant.

The set s constructed to contain the obstacles directly relates to the number of obstacles m. This takes up O(m) space as each obstacle needs one space in the set.

Other variables (dirs, ans, k, x, y, nx, ny) use a constant amount of space, so they do not scale with the input.

Therefore, the space complexity of the code is O(m).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don't know