# Robot Bounded In Circle
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/robot-bounded-in-circle)
Canonical: https://scaleengineer.com/dsa/problems/robot-bounded-in-circle
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Chewy](https://scaleengineer.com/companies/chewy), [Nvidia](https://scaleengineer.com/companies/nvidia), [ZScaler](https://scaleengineer.com/companies/zscaler)
---
## Problem
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 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.

**Example 2:**

**Input:** instructions = "GG"
**Output:** false
**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.
Repeating the instructions, keeps advancing in the north direction and does not go into cycles.
Based on that, we return false.

**Example 3:**

**Input:** instructions = "GL"
**Output:** true
**Explanation:** The robot is initially at (0, 0) facing the north direction.
"G": move one step. Position: (0, 1). Direction: North.
"L": turn 90 degrees anti-clockwise. Position: (0, 1). Direction: West.
"G": move one step. Position: (-1, 1). Direction: West.
"L": turn 90 degrees anti-clockwise. Position: (-1, 1). Direction: South.
"G": move one step. Position: (-1, 0). Direction: South.
"L": turn 90 degrees anti-clockwise. Position: (-1, 0). Direction: East.
"G": move one step. Position: (0, 0). Direction: East.
"L": turn 90 degrees anti-clockwise. Position: (0, 0). Direction: North.
Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (-1, 1) --> (-1, 0) --> (0, 0).
Based on that, we return true.

**Constraints:**

* `1 <= instructions.length <= 100`
* `instructions[i]` is `'G'`, `'L'` or, `'R'`.

# Approaches
## Simulation for Four Cycles
A key observation is that the robot's direction space is cyclic with a period of 4 (North -> East -> South -> West -> North). This implies that after at most 4 cycles of instructions, the robot's net orientation change will have gone through a full 360-degree rotation or a multiple thereof. If the net displacement over these 4 cycles is zero, the robot will have returned to its starting point `(0,0)` and will repeat this meta-cycle forever, hence being bounded. This approach simulates the robot's movement for 4 full cycles and checks if its final position is the origin. This is a correct but suboptimal approach.
**Time:** O(N) - The time complexity is proportional to the length of the instructions string, N. We iterate through the instructions 4 times, so the complexity is O(4 * N), which simplifies to O(N). · **Space:** O(1) - Constant space is used, as we only need a few variables to store the robot's current state (x, y, and direction).
**Pros:** It is a correct algorithm that will pass all test cases.; The implementation is straightforward and follows a simple simulation logic.
**Cons:** Performs more computations than necessary, as the same conclusion can be drawn after just one cycle.; The reasoning behind why 4 cycles is sufficient might be less intuitive than the single-cycle analysis.
### Explanation
This approach is based on the idea that if the robot's path is bounded, its movement must exhibit a repeating pattern over a finite number of cycles. The directions (North, East, South, West) form a cycle of length 4. This suggests that the robot's overall trajectory might also have a period related to 4.

Let the displacement vector after one cycle be `v` and the rotation of the direction be `R`. The position after 4 cycles will be the sum of displacements from each cycle: `p_4 = v + R(v) + R^2(v) + R^3(v)`. It can be mathematically shown that this sum is zero if the direction changes after one cycle (`R` is not the identity rotation). If the direction does not change, the sum is `4v`, which is zero only if `v` is zero. Therefore, checking if the robot is at the origin after 4 cycles is a valid test for boundedness.

```java
class Solution {
    public boolean isRobotBounded(String instructions) {
        // 0: North, 1: East, 2: South, 3: West
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0;
        int dir = 0;

        // Simulate for 4 cycles, carrying over the state
        for (int i = 0; i < 4; i++) {
            for (char instruction : instructions.toCharArray()) {
                if (instruction == 'R') {
                    dir = (dir + 1) % 4;
                } else if (instruction == 'L') {
                    dir = (dir + 3) % 4;
                } else { // 'G'
                    x += dirs[dir][0];
                    y += dirs[dir][1];
                }
            }
        }

        // After 4 cycles, if the robot is at the origin, its path is bounded.
        return x == 0 && y == 0;
    }
}
```
### Algorithm
- Initialize the robot's state: position `(x, y) = (0, 0)` and direction `dir = 0` (representing North).
- Define the displacement vectors for each direction (North, East, South, West).
- Simulate the robot's movement for 4 full cycles of the given instructions.
- In each cycle, iterate through the instructions string and update the robot's position and direction accordingly.
  - For 'G', move one unit in the current direction.
  - For 'L', turn 90 degrees left.
  - For 'R', turn 90 degrees right.
- After completing all 4 cycles, check the robot's final position.
- If the final position is `(0, 0)`, the path is bounded, so return `true`. Otherwise, return `false`.

## Single-Pass Simulation and State Analysis
This approach is based on a mathematical insight into the robot's long-term behavior. The robot's path is bounded if and only if its state after a single cycle of instructions meets one of two conditions: 1. The robot returns to the origin `(0,0)`. 2. The robot's final direction is different from its initial direction (North). We can prove this by considering the net displacement and rotation after one cycle. If the direction changes, the displacement vector rotates with each subsequent cycle, leading to a periodic path. If the direction does not change, the displacement is constant for each cycle, leading to an unbounded path unless the displacement is zero. This allows us to solve the problem by simulating just one cycle, making it the most efficient solution.
**Time:** O(N) - We iterate through the instructions string of length N only once. · **Space:** O(1) - Constant space is used for variables storing the current state.
**Pros:** This is the most efficient solution in terms of time complexity.; The implementation is very simple and concise.; It avoids redundant computations by analyzing the state after a single pass.
**Cons:** The correctness of this approach relies on a mathematical insight that may not be immediately obvious.
### Explanation
The core idea is to analyze the robot's state after just one pass of the instructions. Let the net displacement be `(dx, dy)` and the final direction be `d_final`.

There are two main cases:

1.  **The direction changes after one cycle (`d_final` is not North):** If the robot's orientation changes, the displacement vector for the next cycle will be rotated relative to the first cycle's displacement. This rotation ensures that the path does not extend infinitely in one direction. The sequence of displacement vectors will cancel each other out over 2 or 4 cycles, causing the robot to follow a repeating, bounded path.

2.  **The direction does not change (`d_final` is North):** If the robot ends up facing North again, the displacement `(dx, dy)` will be the same for every subsequent cycle. The robot's position after `k` cycles will be `k * (dx, dy)`. This path is unbounded unless the displacement is zero, i.e., `(dx, dy) = (0, 0)`. In this case, the robot returns to the origin after each cycle and is bounded.

Combining these, the robot is bounded if and only if after one cycle, it has returned to the origin OR it is no longer facing North.

```java
class Solution {
    public boolean isRobotBounded(String instructions) {
        // 0: North, 1: East, 2: South, 3: West
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0;
        int dir = 0; // Initially facing North

        // Simulate for one cycle
        for (char instruction : instructions.toCharArray()) {
            if (instruction == 'R') {
                dir = (dir + 1) % 4;
            } else if (instruction == 'L') {
                dir = (dir + 3) % 4;
            } else { // 'G'
                x += dirs[dir][0];
                y += dirs[dir][1];
            }
        }

        // After one cycle:
        // 1. If robot returns to the origin, it's bounded.
        // 2. If robot's direction has changed, it's bounded.
        // The only case it's unbounded is if it ends up at a non-origin
        // point and is still facing North (dir == 0).
        return (x == 0 && y == 0) || (dir != 0);
    }
}
```
### Algorithm
- Initialize the robot's state: position `(x, y) = (0, 0)` and direction `dir = 0` (representing North).
- Define the displacement vectors for each direction.
- Simulate the robot's movement for exactly one cycle of the given instructions, updating its position and direction.
- After the single cycle, check the final state.
- The robot is bounded if either of these conditions is met:
  1. The final position is the origin `(0, 0)`.
  2. The final direction is not North (i.e., `dir != 0`).
- Return `true` if the condition is met, `false` otherwise.

# Solutions
### Java

```java
class Solution {
public
  boolean isRobotBounded(String instructions) {
    int k = 0;
    int[] dist = new int[4];
    for (int i = 0; i < instructions.length(); ++i) {
      char c = instructions.charAt(i);
      if (c == 'L') {
        k = (k + 1) % 4;
      } else if (c == 'R') {
        k = (k + 3) % 4;
      } else {
        ++dist[k];
      }
    }
    return (dist[0] == dist[2] && dist[1] == dist[3]) || (k != 0);
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isRobotBounded(string instructions) {
    int dist[4]{};
    int k = 0;
    for (char &c : instructions) {
      if (c == 'L') {
        k = (k + 1) % 4;
      } else if (c == 'R') {
        k = (k + 3) % 4;
      } else {
        ++dist[k];
      }
    }
    return (dist[0] == dist[2] && dist[1] == dist[3]) || k;
  }
};

```

### Python

```python
class Solution:
    def isRobotBounded(self, instructions: str) -> bool: k = 0 dist = [0] * 4 for c in instructions: if c == 'L': k = (k + 1) % 4 elif c == 'R': k = (k + 3) % 4 else: dist[k] += 1 return (dist[0] == dist[2] and dist[1] == dist[3]) or k != 0

```