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
andobstacles
respectively. 
Space Complexity: , the space used in storing the
obstacleSet
.
Analysis written by: @awice.