On an infinite plane, a robot initially stands at (0, 0) and faces north. Note that:
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 <= 100instructions[i] is 'G', 'L' or, 'R'.Problem Overview: You control a robot starting at the origin facing north. The instruction string contains G (go forward), L (turn left), and R (turn right). After repeating the instruction sequence infinitely, determine whether the robot stays within a circle or drifts away forever.
Approach 1: Simulate Execution (O(n) time, O(1) space)
Track the robot’s position and direction while executing the instruction string once. Maintain coordinates (x, y) and a direction index representing north, east, south, or west. For every G, move one step in the current direction. For L or R, update the direction using simple modular arithmetic. After processing the full instruction string, check two conditions: the robot returns to the origin, or the robot is not facing north. If either is true, the path forms a cycle and remains bounded.
The key insight: if the robot ends up facing a different direction, repeating the instructions rotates the movement pattern and eventually forms a loop within four cycles. Only when the robot ends one cycle facing north and not at the origin will it continue drifting outward indefinitely. This approach relies purely on simulation with constant memory.
Approach 2: Graphical Analysis with Simulation (O(n) time, O(1) space)
Instead of focusing only on coordinates, reason about the geometric movement pattern. The robot moves on a grid and can face only four orientations. Simulate one pass through the instructions and visualize the path segments. If the robot returns to the origin, the path clearly forms a closed loop. If it finishes facing east, south, or west, the next execution rotates the path and forces the trajectory into a repeating square-like cycle.
This reasoning comes from observing rotational symmetry in grid movements. Four possible orientations mean the path can repeat in at most four cycles. Implement the same direction tracking as the simulation approach, but interpret the result using geometric constraints. The logic connects closely to concepts from math and coordinate transformations while processing the instruction string.
Recommended for interviews: The standard expectation is the single-pass simulation. It runs in O(n) time with O(1) space and demonstrates that you understand both state simulation and the geometric insight behind bounded motion. Interviewers usually want to see the reasoning about orientation changes—showing why a non-north direction guarantees a loop.
The idea is to simulate the movement of the robot step by step according to the given instructions. We maintain the robot's current position and direction. If after one set of instructions, the robot has not returned to its original position but is not facing north, it must eventually form a circle upon repeated execution of the instructions.
Steps include initializing the position and direction, iterating over the instructions to update the position and direction, and finally checking conditions for cycle existence.
In this C solution, we process each instruction using a for loop. The robot's direction is represented as an integer. For 'G', we update coordinates using pre-defined direction deltas. For 'L' and 'R', we simply update the direction modulo 4. Finally, we check if the robot is back at the origin or if it's not facing north to determine if it's bound within a circle.
Time Complexity: O(n), where n is the length of the instructions string, because we iterate through the instructions once.
Space Complexity: O(1), since we use constant extra space for variables.
Here, simulate the robot's actions on the plane for up to four cycles of the input instructions. The observation is that if the robot returns to the starting position or is not facing north, then it will ultimately confine within a bounded circle.
The simulation idea draws from rotational symmetry and periodicity principles in movement patterns over multiple instruction applications.
The C implementation leverages a nested loop with a fixed cycle count determined by directionality. If the robot returns to (0, 0) within four cycles or isn't facing north, it suggests containment within a circle.
Time Complexity: O(4n) = O(n); we simulate up to four full instruction loops.
Space Complexity: O(1), as it only uses constant space independent of input size.
We can simulate the robot's movement. Use a variable k to represent the robot's direction, initialized to 0, which means the robot is facing north. The variable k can take values in the range [0, 3], representing the robot facing north, west, south, and east, respectively. Additionally, we use an array dist of length 4 to record the distance the robot travels in the four directions, initialized to [0, 0, 0, 0].
Traverse the instruction string instructions. If the current instruction is 'L', the robot turns west, i.e., k = (k + 1) bmod 4; if the instruction is 'R', the robot turns east, i.e., k = (k + 3) bmod 4; otherwise, the robot moves one step in the current direction, i.e., dist[k]++.
If the given instruction string instructions is executed once and the robot returns to the origin, i.e., dist[0] = dist[2] and dist[1] = dist[3], then the robot will definitely enter a loop. This is because no matter how many times the instructions are repeated, the robot always returns to the origin, so it must enter a loop.
If the given instruction string instructions is executed once and the robot does not return to the origin, suppose the robot is at (x, y) and its direction is k.
k=0, i.e., the robot is facing north, then after executing the instructions a second time, the coordinate change is (x, y); after executing the instructions a third time, the coordinate change is still (x, y)... Accumulating these changes, the robot will eventually reach (n times x, n times y), where n is a positive integer. Since the robot does not return to the origin, i.e., x neq 0 or y neq 0, it follows that n times x neq 0 or n times y neq 0, so the robot will not enter a loop;k=1, i.e., the robot is facing west, then after executing the instructions a second time, the coordinate change is (-y, x); after executing the instructions a third time, the coordinate change is (-x, -y); after executing the instructions a fourth time, the coordinate change is (y, -x). Accumulating these coordinate changes, we find that the robot will eventually return to the origin (0, 0);k=2, i.e., the robot is facing south, then after executing the instructions a second time, the coordinate change is (-x, -y). Accumulating these two coordinate changes, we find that the robot will eventually return to the origin (0, 0);k=3, i.e., the robot is facing east, then after executing the instructions a second time, the coordinate change is (y, -x); after executing the instructions a third time, the coordinate change is (-x, -y); after executing the instructions a fourth time, the coordinate change is (-y, x). Accumulating these coordinate changes, we find that the robot will eventually return to the origin (0, 0).In conclusion, if the given instruction string instructions is executed once and the robot returns to the origin, or if the robot's direction is different from the initial direction, then the robot will definitely enter a loop.
The time complexity is O(n), and the space complexity is O(1), where n is the length of the instruction string instructions.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Simulate Execution | Time Complexity: O(n), where n is the length of the instructions string, because we iterate through the instructions once. |
| Graphical Analysis with Simulation | Time Complexity: O(4n) = O(n); we simulate up to four full instruction loops. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Execution | O(n) | O(1) | Best general solution. Track position and direction in one pass. |
| Graphical Analysis with Simulation | O(n) | O(1) | When explaining the geometric reasoning behind why the robot stays bounded. |
Robot Bounded in Circle - Math & Geometry - Leetcode 1041 - Python • NeetCode • 46,446 views views
Watch 9 more video solutions →Practice Robot Bounded In Circle with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor