Code Implementation

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        # Directions: North, East, South, West
        directions = [(0,1), (1,0), (0,-1), (-1,0)]
        x, y = 0, 0
        dir_idx = 0  # Start facing North

        for ch in instructions:
            if ch == 'G':
                dx, dy = directions[dir_idx]
                x += dx
                y += dy
            elif ch == 'L':
                dir_idx = (dir_idx + 3) % 4  # Turn left
            else:  # ch == 'R'
                dir_idx = (dir_idx + 1) % 4  # Turn right

        # If back at the origin or not facing North, it's bounded
        return (x == 0 and y == 0) or dir_idx != 0
      

class Solution {
public:
    bool isRobotBounded(string instructions) {
        // Directions: North, East, South, West
        vector<pair<int,int>> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        int x = 0, y = 0, dir = 0; // Start at (0,0) facing North

        for (char ch : instructions) {
            if (ch == 'G') {
                x += directions[dir].first;
                y += directions[dir].second;
            } else if (ch == 'L') {
                dir = (dir + 3) % 4; // Turn left
            } else { // 'R'
                dir = (dir + 1) % 4; // Turn right
            }
        }
        // Bounded if back at origin or not facing North
        return (x == 0 && y == 0) || dir != 0;
    }
};
      

class Solution {
    public boolean isRobotBounded(String instructions) {
        // Directions: North, East, South, West
        int[][] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        int x = 0, y = 0, dir = 0; // Start at (0,0) facing North

        for (char ch : instructions.toCharArray()) {
            if (ch == 'G') {
                x += directions[dir][0];
                y += directions[dir][1];
            } else if (ch == 'L') {
                dir = (dir + 3) % 4; // Turn left
            } else { // 'R'
                dir = (dir + 1) % 4; // Turn right
            }
        }
        // Bounded if back at origin or not facing North
        return (x == 0 && y == 0) || dir != 0;
    }
}
      

var isRobotBounded = function(instructions) {
    // Directions: North, East, South, West
    const directions = [[0,1], [1,0], [0,-1], [-1,0]];
    let x = 0, y = 0, dir = 0; // Start at (0,0) facing North

    for (const ch of instructions) {
        if (ch === 'G') {
            x += directions[dir][0];
            y += directions[dir][1];
        } else if (ch === 'L') {
            dir = (dir + 3) % 4; // Turn left
        } else { // 'R'
            dir = (dir + 1) % 4; // Turn right
        }
    }
    // Bounded if back at origin or not facing North
    return (x === 0 && y === 0) || dir !== 0;
};
      

Problem Description

Given a string instructions consisting only of the characters 'G' (go straight), 'L' (turn left 90 degrees), and 'R' (turn right 90 degrees), a robot starts at the origin (0, 0) facing north. It executes the sequence of instructions repeatedly and infinitely. The task is to determine whether the robot stays within a circle (i.e., is bounded in a circle) or whether it will wander off to infinity.

Key constraints:

• The robot always starts at (0, 0) facing north.
• Instructions are repeated infinitely.
• Return true if the robot is bounded in a circle, otherwise false.

Thought Process

At first glance, it might seem like we need to simulate the robot's movement for a very long time or even infinitely to see if it stays within a circle. However, that would be too slow and inefficient. Instead, we should look for patterns or invariants that allow us to determine boundedness after just one pass of the instructions.

Let's consider what can happen after one full iteration of the instruction string:

• If the robot returns to the origin, then repeating the instructions will keep it in a loop, so it is bounded.
• If the robot doesn't return to the origin but is facing a different direction, then after repeating the instructions enough times, it will eventually return to the origin or form a cycle, so it is still bounded.
• If the robot doesn't return to the origin and is still facing north, it will keep moving away from the origin with each repetition, so it is unbounded.

Solution Approach

Here’s how we solve the problem step-by-step:

1. Track Position and Direction:
   • We use variables x and y to represent the robot's current coordinates.
   • We use an index dir to represent the robot's current direction: 0 for north, 1 for east, 2 for south, 3 for west.
2. Define Direction Movement:
   • We use an array to map the direction index to coordinate changes: north = (0,1), east = (1,0), south = (0,-1), west = (-1,0).
3. Simulate One Pass of Instructions:
   • For each character in instructions:
   • If 'G', move forward in the current direction.
   • If 'L', turn left (decrement direction index, wrapping around).
   • If 'R', turn right (increment direction index, wrapping around).
4. Check Boundedness:
   • After one pass, check the robot's position and direction.
   • If it’s back at the origin (x == 0 && y == 0), it is bounded.
   • If it’s not at the origin but not facing north (dir != 0), it is also bounded because repeating the instructions will eventually return it to the origin or form a cycle.
   • If neither condition is met, it is unbounded.

This approach is efficient and only requires a single pass through the instruction string.

Example Walkthrough

Let's walk through an example with instructions = "GLR":

• Start at (0,0), facing north (dir=0).
• First instruction: 'G' → move north to (0,1).
• Second instruction: 'L' → turn left, now facing west (dir=3).
• Third instruction: 'R' → turn right, now facing north again (dir=0).

After one pass, the robot is at position (0,1), facing north. Since it's not at the origin and still facing north, repeating the instructions will move it further away (to (0,2), (0,3), etc.), so it is not bounded.

Now consider instructions = "GL":

• Start at (0,0), facing north.
• 'G' → (0,1), facing north.
• 'L' → still at (0,1), now facing west.

After one pass, the robot is at (0,1), facing west. Since it's not facing north, repeating the instructions will make the robot trace a square, eventually returning to the origin. So it is bounded.

Time and Space Complexity

Brute-force approach: If we tried to simulate the robot's movement for many cycles, the time complexity would be O(N * K), where N is the instruction length and K is the number of cycles simulated (potentially very large or infinite).

Optimized approach (our solution):

• Time Complexity: O(N), where N is the length of instructions, because we only loop through the instructions once.
• Space Complexity: O(1), as we only use a constant number of variables for position and direction.

Summary

The key insight for this problem is that you only need to simulate the instructions once and check the robot's position and orientation. If the robot is back at the origin or not facing north, it will stay bounded in a circle. This leads to an elegant O(N) solution that avoids unnecessary repeated simulation and leverages the cyclical nature of the robot's possible states.