Robot Bounded In Circle
MedPrompt
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 <= 100instructions[i]is'G','L'or,'R'.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize the robot's state: position
(x, y) = (0, 0)and directiondir = 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 returntrue. Otherwise, returnfalse.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Initialize the robot's state: position
(x, y) = (0, 0)and directiondir = 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:
- The final position is the origin
(0, 0). - The final direction is not North (i.e.,
dir != 0).
- The final position is the origin
- Return
trueif the condition is met,falseotherwise.
Walkthrough
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:
-
The direction changes after one cycle (
d_finalis 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. -
The direction does not change (
d_finalis 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 afterkcycles will bek * (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.
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); }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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); }}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; }};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 != 0Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.