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 left90
degrees.-1
: Turn right90
degrees.1 <= k <= 9
: Move forwardk
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].
Example 1:
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:
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:
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.
Constraints:
1 <= commands.length <= 104
commands[i]
is either-2
,-1
, or an integer in the range[1, 9]
.0 <= obstacles.length <= 104
-3 * 104 <= xi, yi <= 3 * 104
- The answer is guaranteed to be less than
231
.
Approach 01:
-
C++
-
Python
#include <vector> #include <unordered_set> #include <algorithm> class Solution { public: // Simulates the movement of a robot according to given commands and obstacles. // Returns the maximum squared Euclidean distance from the origin that the robot reaches. int robotSim(std::vector<int>& commands, std::vector<std::vector<int>>& obstacles) { // Direction vectors for north, east, south, west. int directionOffsets[5] = {0, 1, 0, -1, 0}; // The last '0' is to allow easy access to 'y' direction with directionOffsets[k+1] // Function to encode a pair of coordinates into a single integer. auto encodePosition = [](int x, int y) { return x * 60010 + y; }; // Set to hold the encoded locations of the obstacles. std::unordered_set<int> obstaclePositions; for (const auto& obstacle : obstacles) { obstaclePositions.insert(encodePosition(obstacle[0], obstacle[1])); } // Initialize variables to track the maximum Euclidean distance squared // and the current direction index and coordinates of the robot. int maxDistanceSquared = 0; int currentDirectionIndex = 0; int currentX = 0, currentY = 0; // Robot starts at the origin (0,0) // Iterate through each command to move the robot. for (int command : commands) { if (command == -2) { // -2 means turn left 90 degrees currentDirectionIndex = (currentDirectionIndex + 3) % 4; // rotate left in the directionOffsets array } else if (command == -1) { // -1 means turn right 90 degrees currentDirectionIndex = (currentDirectionIndex + 1) % 4; // rotate right in the directionOffsets array } else { // Move forward by 'command' steps. while (command--) { // Loop over each step. // Calculate the next x and y after moving a step in the current direction. int nextX = currentX + directionOffsets[currentDirectionIndex]; int nextY = currentY + directionOffsets[currentDirectionIndex + 1]; // Check if the next position is an obstacle. if (obstaclePositions.count(encodePosition(nextX, nextY))) { break; // An obstacle blocks further movement in this direction. } // Update the robot's current position. currentX = nextX; currentY = nextY; // Update the maximum distance squared if necessary. maxDistanceSquared = std::max(maxDistanceSquared, currentX * currentX + currentY * currentY); } } } // Return the maximum Euclidean distance squared that the robot has been from the origin. return maxDistanceSquared; } };
from typing import List, Set class Solution: def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int: # Direction vectors for north, east, south, west. directionOffsets = [0, 1, 0, -1, 0] # The last '0' allows easy access to 'y' direction with directionOffsets[k+1] # Function to encode a pair of coordinates into a single integer. def encodePosition(x: int, y: int) -> int: return x * 60010 + y # Set to hold the encoded locations of the obstacles. obstaclePositions: Set[int] = {encodePosition(obstacle[0], obstacle[1]) for obstacle in obstacles} # Initialize variables to track the maximum Euclidean distance squared # and the current direction index and coordinates of the robot. maxDistanceSquared = 0 currentDirectionIndex = 0 currentX, currentY = 0, 0 # Robot starts at the origin (0, 0) # Iterate through each command to move the robot. for command in commands: if command == -2: # -2 means turn left 90 degrees currentDirectionIndex = (currentDirectionIndex + 3) % 4 # Rotate left in the directionOffsets array elif command == -1: # -1 means turn right 90 degrees currentDirectionIndex = (currentDirectionIndex + 1) % 4 # Rotate right in the directionOffsets array else: # Move forward by 'command' steps. while command > 0: # Loop over each step. # Calculate the next x and y after moving a step in the current direction. nextX = currentX + directionOffsets[currentDirectionIndex] nextY = currentY + directionOffsets[currentDirectionIndex + 1] # Check if the next position is an obstacle. if encodePosition(nextX, nextY) in obstaclePositions: break # An obstacle blocks further movement in this direction. # Update the robot's current position. currentX, currentY = nextX, nextY # Update the maximum distance squared if necessary. maxDistanceSquared = max(maxDistanceSquared, currentX * currentX + currentY * currentY) # Decrement the remaining steps to move forward. command -= 1 # Return the maximum Euclidean distance squared that the robot has been from the origin. return maxDistanceSquared
Time Complexity
- Encoding Obstacles:
To encode the positions of obstacles into a hash set, the time complexity is \( O(p) \), where \( p \) is the number of obstacles. This involves iterating through the list of obstacles and inserting each one into the set.
- Processing Commands:
The robot processes each command in the `commands` vector. For each forward movement command (a positive integer), the robot may potentially move one step at a time, checking for obstacles. This results in a worst-case time complexity of \( O(q) \), where \( q \) is the total number of commands.
- Overall Time Complexity:
The total time complexity is \( O(p + q) \), where \( p \) is the number of obstacles and \( q \) is the total number of commands processed.
Space Complexity
- Space for Obstacles:
The hash set `obstaclePositions` stores the encoded positions of all obstacles, resulting in a space complexity of \( O(p) \), where \( p \) is the number of obstacles.
- Space for Direction Offsets and Variables:
Additional space is used for the `directionOffsets` array and a few integer variables (`currentX`, `currentY`, etc.). This requires a constant amount of space, \( O(1) \).
- Overall Space Complexity:
The overall space complexity is \( O(p) \) due to the storage required for the hash set of obstacle positions.