Thomas Ngo

Software Engineer

3 minute read

Problem

problem

Intuition

The robot is controlled by a sequence of commands and should avoid obstacles. We need to simulate its movement step by step, keeping track of its position and direction, while checking for obstacles.

Approach

We start with the robot at position (0, 0) facing north. We can use a set to store obstacles for O(1) lookup. The robot’s movement direction can be controlled by a set of booleans (north, south, west, east), which change based on the left and right turns.

For every movement command:

  1. If the command is a turn (LEFT or RIGHT), we update the direction accordingly.
  2. If the command is a forward move, we check each step until either the number of steps is completed or the robot encounters an obstacle.

We calculate the square of the Euclidean distance from the origin for each new position and track the maximum distance the robot reaches.

Complexity

  • Time complexity:
    The time complexity is \(O(k + n)\), where \(k\) is the number of commands and \(n\) is the number of obstacles. For each command, we perform a constant amount of work, and the obstacle lookups take O(1) time due to the set.

  • Space complexity:
    The space complexity is \(O(n)\) because we need to store all the obstacles in a set for O(1) lookup.

Code

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        x, y = 0, 0
        LEFT = -2
        RIGHT = -1
        is_north = True
        is_south = False
        is_west = False
        is_east = False
        move_y = 1
        move_x = 0
        res = 0
        obstacle_set = set(map(tuple, obstacles)) # important: without this we will get TLE
        for command in commands:
            if is_north:
                if command == RIGHT:
                    move_x = 1
                    is_east = True
                    is_south = is_west = is_north = False
                    move_y = 0
                if command == LEFT:
                    move_x = -1
                    is_west = True
                    is_south = is_east = is_north = False
                    move_y = 0
            elif is_south:
                if command == RIGHT:
                    move_x = -1
                    is_west = True
                    is_south = is_east = is_north = False
                    move_y = 0
                if command == LEFT:
                    move_x = 1
                    is_east = True
                    is_south = is_west = is_north = False
                    move_y = 0
            elif is_west:
                if command == RIGHT:
                    move_y = 1
                    is_north = True
                    is_south = is_east = is_west = False
                    move_x = 0
                if command == LEFT:
                    move_y = -1
                    is_south = True
                    is_north = is_east = is_west = False
                    move_x = 0
            elif is_east:
                if command == RIGHT:
                    move_y = -1
                    is_south = True
                    is_north = is_east = is_west = False
                    move_x = 0
                if command == LEFT:
                    move_y = 1
                    is_north = True
                    is_south = is_east = is_west = False
                    move_x = 0

            if command != LEFT and command != RIGHT:
                next_x, next_y = x, y
                for i in range(1, command + 1):
                    new_x = x + (move_x * i)
                    new_y = y + (move_y * i)
                    if (new_x, new_y) in obstacle_set:
                        break
                    next_x, next_y = new_x, new_y
                x, y = next_x, next_y
                res = max(res, x*x + y*y)
        return res

Editorial

class Solution:
    def __init__(self):
        self.HASH_MULTIPLIER = (
            60001  # Slightly larger than 2 * max coordinate value
        )

    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        # Store obstacles in an set for efficient lookup
        obstacle_set = {self._hash_coordinates(x, y) for x, y in obstacles}

        # Define direction vectors: North, East, South, West
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        x, y = 0, 0
        max_distance_squared = 0
        current_direction = 0  # 0: North, 1: East, 2: South, 3: West

        for command in commands:
            if command == -1:  # Turn right
                current_direction = (current_direction + 1) % 4
                continue

            if command == -2:  # Turn left
                current_direction = (current_direction + 3) % 4
                continue

            # Move forward
            dx, dy = directions[current_direction]
            for _ in range(command):
                next_x, next_y = x + dx, y + dy
                if self._hash_coordinates(next_x, next_y) in obstacle_set:
                    break
                x, y = next_x, next_y

            max_distance_squared = max(max_distance_squared, x * x + y * y)

        return max_distance_squared

    # Hash function to convert (x, y) coordinates to a unique integer value
    def _hash_coordinates(self, x: int, y: int) -> int:
        return x + self.HASH_MULTIPLIER * y

You may also enjoy