Watch 10 video solutions for Robot Bounded In Circle, a medium level problem involving Math, String, Simulation. This walkthrough by NeetCode has 46,446 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |