Skip to main content
Talentd

Robot Bounded In Circle - Solution & Explanation

MediumMathStringSimulation32 min readAsked at: Amazon, Microsoft, Apple +8
Practice this problem

Problem Statement

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'.

Approach Overview

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 1: Simulate Execution

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Graphical Analysis with Simulation

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Simulation

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.

  • If 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;
  • If 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);
  • If 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);
  • If 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simulate Execution

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.

Graphical Analysis with Simulation

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.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulate ExecutionO(n)O(1)Best general solution. Track position and direction in one pass.
Graphical Analysis with SimulationO(n)O(1)When explaining the geometric reasoning behind why the robot stays bounded.

Video Solution

Robot Bounded in Circle - Math & Geometry - Leetcode 1041 - Python • NeetCode • 46,947 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Robot Bounded In Circle easy or hard?
Robot Bounded In Circle is rated Medium on LeetCode. The implementation is straightforward, but the challenge lies in recognizing the key insight: a direction change after one cycle guarantees the robot's path eventually forms a loop.
Robot Bounded In Circle Python/Java solution
Both Python and Java implementations follow the same simulation logic. Iterate through the instruction string, update direction for 'L' and 'R', and move coordinates for 'G'. After one cycle, check whether the robot is back at the origin or facing a different direction.
How to solve Robot Bounded In Circle in O(n)?
Simulate the robot’s movement for one full instruction cycle. Maintain a direction index for north, east, south, and west, and update coordinates when encountering 'G'. After processing all instructions, the robot is bounded if it returns to (0,0) or if its final direction is not north.
What is the best approach for Robot Bounded In Circle?
The most efficient approach is single-pass simulation. Track the robot's coordinates and direction while executing the instruction string once. If the robot ends at the origin or ends facing a direction other than north, the path is bounded. This runs in O(n) time with O(1) space.
Is Robot Bounded In Circle asked at Google/Amazon/Meta?
Robot Bounded In Circle has appeared in interviews at companies that emphasize algorithmic simulation and grid reasoning, including Google and Amazon-style interview sets. It tests state simulation, coordinate tracking, and recognizing repeating patterns.
What data structure is used in Robot Bounded In Circle?
The problem mainly uses simple variables for coordinates and direction tracking rather than complex data structures. Direction is typically stored as an index into a fixed array of direction vectors, while the instructions are processed from the input string.
What is the time complexity of Robot Bounded In Circle?
The optimal solution runs in O(n) time, where n is the length of the instruction string. Each character is processed exactly once during the simulation. Space complexity is O(1) because only coordinates and direction variables are maintained.

Ready to solve this problem?

Practice Robot Bounded In Circle with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer