Approach 1: Simulation
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.
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
Time Complexity: , where are the lengths of
Space Complexity: , the space used in storing the