Problem Statement in English

You’re given an array of integers commands and an array of arrays obstacles, where commands[i] is the i-th command and obstacles[j] = [x, y] is the position of the j-th obstacle.

The commands are interpreted as follows:

  • -2: turn left 90 degrees
  • -1: turn right 90 degrees
  • 1 <= x <= 9: move forward x units

The robot starts at the origin (0, 0) facing north. The robot will not move onto an obstacle, but it can move around it. If the robot tries to move onto an obstacle, it will stay in its current position and continue to execute the next command.

The starting point itself can be an obstacle. If it is, the robot will ignore it initially, but once it leaves the starting point, it will not be able to return to it.

Approach

This is more about an implementation problem than anything else. We just need to simulate the robot’s movement based on the commands and obstacles.

We can represent the robot’s direction as an index in an array of directions, for example ["N", "E", "S", "W"]. When we receive a turn command, we can simply update the index accordingly. For example, if we receive a left turn command, we can decrement the index by 1 (and wrap around using modulo), and if we receive a right turn command, we can increment the index by 1 (and wrap around using modulo).

When we receive a move command, we need to check if the next position is an obstacle. If it is, we need to stop moving and continue with the next command. If it is not, we can move to the next position and update our maximum distance from the origin.

To efficiently check for obstacles, we can store the obstacles in a set for O(1) lookups. We can represent the position of the robot as a tuple (x, y), and we can calculate the next position based on the current direction and the number of steps to move.

To calculate the maximum distance from the origin, we can use the formula $\text{distance} = x^2 + y^2$, since we are only interested in the maximum distance and not the actual distance.

And we’re done!

Solution in Python


class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        dirs = ["N", "E", "S", "W"]

        ptr = res = 0
        pos = [0, 0]

        obstacles = set((x[0], x[1]) for x in obstacles)

        for c in commands:
            if c == -1:
                ptr = (ptr + 1) % 4
            elif c == -2:
                ptr = (ptr - 1) % 4
            else:
                dir = dirs[ptr]
                moves = c

                while moves:
                    backup = pos.copy()

                    if dir == "N":
                        pos[1] += 1
                    elif dir == "E":
                        pos[0] += 1
                    elif dir == "S":
                        pos[1] -= 1
                    elif dir == "W":
                        pos[0] -= 1

                    if (pos[0], pos[1]) in obstacles:
                        pos = backup
                        break

                    res = max(res, pow(pos[0], 2) + pow(pos[1], 2))
                    moves -= 1

        return res

Complexity

  • Time: $O(n + m)$
    Since we are iterating through the commands list once, which takes $O(n)$ time, and we are also iterating through the obstacles list once to create a set, which takes $O(m)$ time. Therefore, the overall time complexity is $O(n + m)$.

  • Space: $O(m)$
    We are creating a set from the obstacles list, which takes $O(m)$ space.

Mistakes I Made

I forgot to make backup a copy of pos, which caused the robot to move into an obstacle and not be able to backtrack.

And we are done.