LeetCode Problem 1041- Robot Bounded In Circle - Level - Medium

LeetCode 1041 - Robot Bounded In a Circle

Today we are going to look at another LeetCode problem  1041 robot bounded in a circle with difficulty level medium.

Problem Statement :

From given problem statement , Robot can perform certain given sets of instruction either G,R,L and corresponding action can be taken. After performing instruction if robot come back to original position (0,0) that means robot will stay in circle and will never leave it.

Let's understand more in details about behaviour of robot.

Robot is standing at position (0,0) coordinates and facing North. 

G >> Move One Step Ahead. That mens increment Y coordinate by One.

R >> Rotate Robot to 90 degree right but stay there.

L >> Rotate robot on left with 90. 

Let's understand this problem by example given in problem statement.

Command : GGLLGG

Step 1 : First robot gets input at GG which means robot will move 2 step ahead by incrementing Y coordinates. So current position of robot will be (X,Y) = (0,2).

But important things to note here is that , Robot is still facing North in Y direction.

Step 2 : Now robot gets two LL command which means robot will rotate 180 degree (90 degree for each ) towards left direction. Now robot after rotation robot will face downwards.

Finally Robot is standing at (0, 2) coordinates facing downwards.  

Step 3 : Now robot receives GG command again , since robot is facing downward , Y coordinates will be subtracted and robot will move back to position (0, 0).

Now no matter how many times robot executes command recursively , it will always come back to same position which means if circle exists in plane then robot will never leave Circle.

While writing code , tricky part is here whether to add or subtract values from (X,Y) which clearly dependent up rotation in which direction robot is facing . 

For Example if robot is facing WEST and G command given then X will be decremented and Y will remains as it is.

Above image gives an idea how to calculate next value to be added/subtracted from robots X,Y coordinates.

Formula : 

On L = (X ,Y) = (-Y , X)

On R = (X, Y) = (Y, -X)

We will use same formulate in our code to determine next move for Robot. 

There is one exception , after performing commands execution if robot still faces North direction then it means robot will leave circle and move indefinitely. 

Complete Solution :

class Solution {
    public boolean isRobotBounded(String instructions) {
      
        int facingX = 0;
        int facingY = 1;
        int x = 0;
        int y = 0;


        for (int index = 0; index < instructions.length(); index++) {
            String c = String.valueOf(instructions.charAt(index));

            if (c.equalsIgnoreCase("G")) {
                x = x + facingX;
                y = y + facingY;
            } else if (c.equalsIgnoreCase("L")) {
                int tmp = facingX;
                facingX = -1 * facingY;
                facingY = tmp;
            } else if (c.equalsIgnoreCase("R")) {
                int tmp = facingX;
                facingX = facingY;
                facingY = -1 * tmp;
            }


        }

        if (x == 0 && y == 0) // Robot back to (0,0), return true.
            return true;

        if (facingX == 0 && facingY == 1) // Robot facing North , it will go out of circle.
            return false;

        return true;
    }
}

Complexity will be O(n) since we are going through command only once.

Keep Learning , Keep Sharing ... !!!