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'.The key idea in #1041 Robot Bounded In Circle is to simulate the robot's movement based on the instruction string. The robot starts at the origin facing north and processes commands like G (go forward), L (turn left), and R (turn right). Instead of repeating the instructions indefinitely, observe what happens after executing the instruction sequence once.
Track the robot’s position and direction using simple variables. If the robot returns to the origin after one cycle, it is clearly bounded within a circle. Even if it does not return to the origin, it can still be bounded if its final direction is different from north, because repeating the instructions will eventually loop its path.
This approach relies on string traversal and direction simulation, making it efficient and easy to implement. The instruction string is processed once, giving a time complexity of O(n) and constant space usage of O(1).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single Pass Simulation of Robot Movement | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Calculate the final vector of how the robot travels after executing all instructions once - it consists of a change in position plus a change in direction.
The robot stays in the circle if and only if (looking at the final vector) it changes direction (ie. doesn't stay pointing north), or it moves 0.
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.
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.
1#include <stdbool.h>
2#include <string.h>
3
4bool isRobotBounded(char * instructions) {
5 int x = 0, y =
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.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of simulation and reasoning problem is common in technical interviews, including FAANG-style questions. It tests understanding of direction handling, pattern observation, and efficient simulation.
If the robot finishes facing a direction other than north, repeating the instructions will rotate its movement pattern. Over multiple cycles, these rotations form a loop that keeps the robot within a bounded region.
No complex data structures are required. Simple variables for coordinates and direction tracking are enough, along with basic string traversal to process each instruction.
The optimal approach is to simulate the robot's movement for one full instruction cycle while tracking its position and direction. If the robot ends at the origin or faces a direction other than north, its path will remain bounded when the instructions repeat.
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.