Robot Bounded In Circle LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Airbnb Amazon Apple Bloomberg Expedia Goldman Sachs Google MicrosoftViews 3137

Problem Statement

Robot Bounded In Circle LeetCode Solution – On an infinite plane, a robot initially stands at (0, 0) and faces north. Note that:

  • The north direction is the positive direction of the y-axis.
  • The south direction is the negative direction of the y-axis.
  • The east direction is the positive direction of the x-axis.
  • The west direction is the negative direction of the x-axis.

The robot can receive one of three instructions:

  • "G": go straight 1 unit.
  • "L": turn 90 degrees to the left (i.e., anti-clockwise direction).
  • "R": turn 90 degrees to the right (i.e., clockwise direction).

The robot performs the instructions given in order and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example

Test Case 1:

Input:

instructions = “GGLLGG”

Output:

true

Explanation

The robot is initially at (0, 0) facing the north direction.

“G”: move one step. Position: (0, 1). Direction: North.

“G”: move one step. Position: (0, 2). Direction: North.

“L”: turn 90 degrees anti-clockwise. Position: (0, 2). Direction: West.

“L”: turn 90 degrees anti-clockwise. Position: (0, 2). Direction: South.

“G”: move one step. Position: (0, 1). Direction: South.

“G”: move one step. Position: (0, 0). Direction: South.

Repeating the instructions, the robot goes into the cycle: (0, 0) –> (0, 1) –> (0, 2) –> (0, 1) –> (0, 0). Based on that, we return true.

Approach:

The problem is somewhat simple to understand if you draw out and run a few examples.

You would realize that a given sequence of instructions would keep the robot bounded in a circle IFF at the end of the first iteration:
Case 1: It has returned to the initial position (0, 0) OR
Case 2: It did not return to the initial position AND does not face the initial direction (up)

In the first case, it is clear that after every iteration of instructions, the robot would be back at 0, 0. This assures that the robot would be bounded by some circle (example 1).

In the second case, the robot will always move away from the initial position IF its direction is the same as the initial direction (example 3); otherwise, the robot will return to the same position in some further iteration of instructions (example 2).

Each of the 3 examples below shows 2 iterations of instructions.
Examples —- 1: GGLLGG, 2: LLGRGL, 3: LLGRGR

Robot Bounded In Circle LeetCode Solution

Based on the two valid cases discussed above, we need to maintain the position of the robot (or its distance relative to the origin) and its direction.

The solution also makes important use of Java’s Math.floorMod method which works similar to Python’s ‘%’ operator.
It is important to NOT use Java’s ‘%’ operator here since it works as a remainder and not a true modulo.

Code for Robot Bounded In Circle

Java Program

class Solution {
    public boolean isRobotBounded(String instructions) {
        // we consider the 4 directions as: 0 = Up, 1 = Right, 2 = Down, 3 = Left
    
        int dirCounter = 0; // Initially facing Up
    // dirCounter will be incremented for a Right turn & decremented for a Left turn
    // so dirCounter 5 indicates that the robot is facing Right (dirCounter mod 4 = 1)
    
        int[] walked = new int[2];
    // This array will maintain the distance travelled on Y and X axes (from origin)
    // walked[0] -> Y distance, walked[1] -> X distance
    
        for(char c : instructions.toCharArray()) {

            if(c == 'G') {
                
        int dir = Math.floorMod(dirCounter, 4);
        // Java's floorMod gives a true MODULO (like Python's %), whereas Java's % operator gives a REMAINDER
        // floorMod for any positive divisor is always positive
        // so, for dirCounter = -5 (i.e. 5 resultant Left), dir = -5 mod 4 = 3 (i.e. Left)
        // Note: -5 % 4 = -1 (not 3)
  
                walked[dir % 2] += (dir == 0 || dir == 1) ? 1 : -1;
        // dir % 2 = 0 for Y axis (i.e. if dir = 0 or 2)
        // dir % 2 = 1 for X axis (i.e. if dir = 1 or 3)
        // if dir = 0 (Up) or 1 (Right), increment walked distance across X or Y
                // else, decrement walked distance along X or Y
                
            }
            else // when c = 'R' or 'L'
      
                dirCounter += c == 'R' ? 1 : -1;
        // Increment or decrement dirCounter based on 'R' or 'L' respectively
    
        }
        
        return (walked[0] == 0 && walked[1] == 0) || Math.floorMod(dirCounter, 4) != 0;
    // Case 1: walked distance along Y and X is 0
    // Case 2: case 1 is false AND final direction is not Up
    }
}

C++ Program

class Solution {
public:
    bool isRobotBounded(string instructions) {
        int size = instructions.size();
        if (size == 0) return true;
        pair<int,int> pos = {0,0};
        int d = 0; // current direction;

        for (int i = 0; i < size; ++i) {
          if (instructions[i] == 'L') d = (d+1)%4;//change direction
          else if (instructions[i] == 'R') d = (d+3)%4;// change direction
          else {// transport 
      if (d == 0) pos.second++;
      else if (d == 1) pos.first--;
      else if (d == 2) pos.second--;
      else if (d == 3) pos.first++;
          }
        }
        // check position and direction;
        if (d!=0) return true;
        if (d == 0 && pos.first==0 && pos.second == 0) return true; 

        return false;
    }
};

Complexity Analysis for Robot Bounded In Circle LeetCode Solution

Time Complexity: O(n)

Space Complexity: O(1)

Translate »