#1041

Medium

LeetCode Problem Workspace

Robot Bounded In Circle

Determine if a robot following a repeated instruction sequence stays within a bounded circle using math and string simulation.

math string simulation

Problem Statement

A robot starts at coordinates (0, 0) on an infinite plane, initially facing north. It can move and rotate based on a sequence of instructions, with each instruction being one of 'G', 'L', or 'R'.

The robot executes the given instruction string repeatedly forever. 'G' moves it one step in its current direction, 'L' rotates it 90 degrees counterclockwise, and 'R' rotates it 90 degrees clockwise. Determine whether the robot stays within some circle on the plane, or if it can wander infinitely far.

Examples

Example 1

Input: instructions = "GGLLGG"

Output: true

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

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

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

Solution Approach

Simulate Single Cycle

Parse the instruction string once, updating the robot's position (x, y) and direction. Track how each 'G', 'L', and 'R' modifies the coordinates and orientation to identify whether the movement forms a closed loop.

Check Orientation

After executing the instruction sequence, check if the robot is back at the origin or facing a direction different from north. If the orientation has changed, repeating the instructions will eventually cycle the robot back, ensuring it stays bounded.

Return Bounded Result

If the robot ends at the origin or faces a new direction, return true indicating it is bounded in a circle. Otherwise, return false because repeating the path causes it to move infinitely away, the core failure mode of misjudging direction changes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for parsing the instruction string of length n, with constant time updates per instruction. Space complexity is O(1) since only position and direction counters are maintained without storing full paths.

What Interviewers Usually Probe

Asks if robot returns to origin or changes direction after one instruction pass.
Mentions efficiency in detecting infinite movement without full simulation.
Hints at combining string parsing with vector math to predict cyclic behavior.

Common Pitfalls or Variants

Common pitfalls

Failing to consider orientation change as a bounding factor, not just returning to origin.
Incorrectly simulating infinite repetitions instead of analyzing one full cycle.
Misupdating coordinates or direction when turning 'L' or 'R', leading to wrong conclusions.

Follow-up variants

Check bounded movement for 3D plane with rotations in multiple axes.
Allow variable step sizes for 'G' and determine bounded trajectories.
Include diagonal movement commands and assess cycle closure using vector math.

FAQ

What is the core pattern behind Robot Bounded In Circle?

The key pattern is analyzing one full instruction sequence with math plus string logic to see if the robot either returns to the origin or changes direction.

Why does the robot stay bounded if it changes direction?

Changing direction ensures that repeated execution rotates the path, eventually cycling back toward the origin, forming a bounded trajectory.

Can the instruction string be empty or extremely long?

Constraints guarantee 1 <= instructions.length <= 100, and each character is 'G', 'L', or 'R', so empty strings are invalid and length is manageable.

How does math combine with string simulation here?

String simulation parses each command, updating position and direction, while math evaluates the net vector and cyclic behavior to determine boundedness.

Is returning to origin the only condition for being bounded?

No, returning to origin or facing a different direction after one cycle are both sufficient to guarantee that repeated execution stays within a circle.

terminal

Solution

Solution 1: 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]$.

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 != 0

Continue Practicing

#640 solve the equation #592 fraction addition and subtraction #537 complex number multiplication