Domain 2MediumMEDIUM

Robot Bounded In Circle

Determine if the robot's path is bounded by checking its position and orientation after one full cycle of instructions.

Domain: medium•Updated: 2026-09-07
#simulation#geometry#O(N)#O(1)

Problem Breakdown

The problem asks us to determine if a robot’s path remains within a finite circle on an infinite plane when its instruction sequence repeats infinitely.

Inputs: A string instructions consisting of ‘G’ (move forward), ‘L’ (turn left 90°), and ‘R’ (turn right 90°). Outputs: Boolean (true if bounded, false otherwise).

Implicit Constraints & Edge Cases:

  • Infinite Plane: We don’t need to check for physical boundaries; we only care about whether the displacement vector grows indefinitely.
  • Initial State: Robot starts at (0, 0) facing North (positive Y-axis in standard Cartesian coordinates).
  • Repetition: The sequence repeats forever. This implies periodic behavior analysis rather than infinite simulation.
  • Constraints: instructions.length is between 1 and 100. We must handle cases where the robot moves away immediately vs. turns around quickly.

Intuition

A brute-force approach would be to simulate the robot’s movement for a very large number of cycles (e.g., 4×N4 \times N) or until it exceeds some coordinate limit. However, since we don’t know how many times it takes to loop back if at all, simulating indefinitely leads to Time Limit Exceeded (TLE).

Key Insight: The robot’s orientation is discrete and finite: there are only 4 possible directions (North, East, South, West).

  1. Case A: If after one full cycle of instructions the robot returns exactly to (0, 0), it will repeat this path forever within a bounded circle.
  2. Case B: If the robot does not return to (0, 0) but its final orientation is different from North (the starting direction), then over time (11 to 44 cycles max), the displacement vectors will rotate and cancel each other out geometrically. The path forms a closed polygon eventually.
  3. Case C: If the robot does not return to (0, 0) AND its final orientation is still North (same as start), it means there was no net rotation in direction combined with non-zero displacement. It will drift away indefinitely along that axis.

Therefore, we only need to simulate exactly one cycle of instructions and check these two conditions at the end.

Approach

  1. Initialize position (x, y) to 0 and current velocity vector (dx, dy) representing facing North (dy = 1, dx = 0).

  2. Iterate through each character in instructions:

    • If 'G': Update position by adding the current direction vector.
    • If 'L': Rotate the direction vector counter-clockwise (90°). Mathematically: (new_dx, new_dy) = (-dy, dx).
    • If 'R': Rotate clockwise (90°): (new_dx, new_dy) = (dy, -dx).
  3. After the loop finishes one cycle of instructions:

    • Check if x == 0 and y == 0. Return True immediately.
    • If not at origin, check if the direction vector changed from North ((0, 1)). Since we track (dx, dy), checking if it is still (0, 1) tells us if orientation remained unchanged relative to start (modulo rotation logic). Actually simpler: Check if x == 0 and y == 0 OR the final direction vector is not North.
    • Wait, strictly speaking: If we track absolute angle or just check against initial state? Let’s refine condition B: The robot is bounded iff (pos != (0,0) AND dir_changed) OR pos == (0,0). Actually, simpler logic derived from math proofs for this problem: Return True if x==0 and y==0, else return True if the final direction vector is not North. If it is facing North but off-origin -> False.
  4. Combine these checks into a single boolean expression at the end of simulation.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of instructions. We iterate through the instruction string exactly once to simulate one cycle. The check logic is constant time.
  • Space Complexity: O(1)O(1). We use a fixed number of variables (x, y, dx, dy) regardless of input size.

Solution

def isRobotBounded(instructions: str) -> bool:
    # Initial state: at origin (0, 0), facing North (+Y direction).
    x, y = 0, 0
    
    # Current velocity vector representing the current heading.
    # Facing North means moving in +y direction initially.
    dx, dy = 0, 1 
    
    for move in instructions:
        if move == 'G':
            # Move forward by updating position based on current facing direction
            x += dx
            y += dy
        elif move == 'L':
            # Turn Left (Counter-Clockwise rotation of velocity vector)
            # Rotation matrix 90 deg CCW: [x, y] -> [-y, x]
            dx, dy = -dy, dx
        else: # move == 'R'
            # Turn Right (Clockwise rotation of velocity vector)
            # Rotation matrix 90 deg CW: [x, y] -> [y, -x]
            dx, dy = dy, -dx
            
    # The robot is bounded if it returns to origin OR its direction changed.
    # If x==0 and y==0, it's definitely bounded (cycle repeats exactly).
    # If not at origin but facing a different direction than North ((0,1)), 
    # the path will eventually loop back due to vector rotation over 4 cycles max.
    return (x == 0 and y == 0) or (dx != 0 or dy != 1)

Edge Cases Handled

  • All ‘G’ instructions: Robot moves North indefinitely, dx remains (0,1) but position changes. Returns False. Correct.
  • “GL” sequence: Moves to (0,1), turns West ((-1, 0)). Position not origin, direction changed from North. Returns True. Correct (forms a loop over time).
  • Empty instructions: Constraints say length >= 1, but logic holds: returns True if empty string implies no movement? Actually constraints prevent this, code assumes valid input per LeetCode spec.
  • “LRLR” sequence: Robot turns in place without moving (x=0, y=0). Returns True. Correct (bounded at origin).