Alex And Infinity Circle

We can observe that, if the person follows the given instructions one time in a printed sheet, if he arrives at his home i.e., his destination, then we can clearly say that our answer is 'True'.

If not, the above case is 'True' , let's simulate the walk of Alex in terms of variables,

Let's say our initial position is ('PosX', 'PosY') in terms of coordinates and denote the change in the direction of x by dx and y by dy.

So dx and dy can be represented by {{0, 1}, {1, 0}, {0, -1}, { -1, 0}}

E.g., initially Alex is facing north. If he walks in the same direction his coordinates will become,

(0,0) -> (0 + 0 , 0 + 1), or we could say ‘PosX’ := ‘PosX’ + dx[dir][0] and ‘PosY’ := ‘PosY’ + dy[dir][1], here dir is denoting direction he is facing, for dir:= 0, 1, 2, 3 it is representing

North, East,  South, West, respectively.

Hence we could say that following instruction 'R' i.e., turn towards the right direction, can be called as 'dir' := ('dir' + 1) % 4, and following instruction 'L,' i.e., turn towards the left direction can be called as 'dir' := ('dir' - 1) % 4, we could also write it as 'dir' := ('dir' + 3) % 4

Now we could see that, and if 'dir' is equal to 0, after following the instruction and new coordinates are (NX, NY), both NX and NY denotes change or delta in coordinates of initial position i.e., (0,0), so following the same set of instructions K times, he will end up at (0 + k * NX, 0 + k * NY), so we can clearly see that Alex can never return to his home.

Now, if dir is not equal to 0, i.e., he ends up in a different direction than he was facing initially, we can claim that he will return to his home i.e., we can return 'True' safely, by following the instructions one or three times, let’s try to prove our claim we made.

Case 1: he ended up facing south, or if the value of 'dir' is 2 , so we can see that after following the same set of instructions, change in coordinates after executing instruction one more times we can say that it will be (-NX,-NY), so the total change becomes, (NX + (-NX) , NY + (-NY)) i.e., (0,0) so he will definitely be returning to his home.

Case 2: he ended up facing east or west, in this case, he will require 3 more iterations to return home, and the changes will become (NX + (-NY) + (-NX) + NY), NY + (-NX) + (-NY) + NX), i.e., equal to (0,0), here NX, NY denotes change after the first iteration, and we have denoted all the changes for each iteration together in a consecutive manner.

The steps of simulation can be called as follows: 

1. Declare an 2-D array/list Direction ‘DIR’ = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}}.
2. Declare three variables and initialize them with ‘currDir’ = 0, ‘PosX’ = 0, ‘PosY’ = 0 that denotes our current direction, current  x-coordinate , y-coordinate respectively.
3. Run a loop for ‘i’ = 0 to length of ‘STR’ -1 :
   • ‘curChar’ = ‘STR[i]’.
   • If ‘curChar’ is equal to ‘R’:
     • ‘currDir’ = ( ‘currDir’ + 1) % 4.
   • Else If ‘curChar’ is equal to ‘L’:
     • ‘currDir’ = ( ‘currDir’ + 3 ) % 4.
   • Else:
     • ‘PosX’  += D[‘currDir’][0].
     • ‘PosY’  += D[‘currDir’][1].
4. If ‘PosX’ is equal to 0 and ‘PosY’ is equal to  0:
   • return True.
5. If ‘currDir’ is not equal to 0 :
   • return True.
6. Finally, return False.

O(N), where ‘N’ is the length of string ‘STR’.

We are traversing on string ‘STR’ only once which takes O(N) time. Hence the overall time complexity is O(N).

O(1).

we are not using any extra space for finding our answer. Hence, the overall space complexity is O(1).