Solution


Approach 1: Simulation

Intuition

We simulate the path of the robot step by step. Since there are at most 90000 steps, this is efficient enough to pass the given input limits.

Algorithm

We store the robot's position and direction. If we get a turning command, we update the direction; otherwise we walk the specified number of steps in the given direction.

Care must be made to use a Set data structure for the obstacles, so that we can check efficiently if our next step is obstructed. If we don't, our check is point in obstacles could be ~10,000 times slower.

In some languages, we need to encode the coordinates of each obstacle as a long integer so that it is a hashable key that we can put into a Set data structure. Alternatively, we could also encode the coordinates as a string.

Complexity Analysis

  • Time Complexity: , where are the lengths of commands and obstacles respectively.

  • Space Complexity: , the space used in storing the obstacleSet.


Analysis written by: @awice.