LeetCode 1041 - Robot Bounded In Circle

This problem asks us to determine whether a robot moving on an infinite two dimensional plane will remain within some bounded region if it repeats a sequence of instructions forever. The robot starts at coordinate (0, 0) facing north.

leetcodemediummathstringsimulation

LeetCode Problem 1041

Difficulty: 🟡 Medium
Topics: Math, String, Simulation

Solution

Problem Understanding

This problem asks us to determine whether a robot moving on an infinite two dimensional plane will remain within some bounded region if it repeats a sequence of instructions forever.

The robot starts at coordinate (0, 0) facing north. The input is a string called instructions, where each character represents an action:

  • 'G' means move forward by one unit in the current direction.
  • 'L' means rotate 90 degrees to the left.
  • 'R' means rotate 90 degrees to the right.

The robot executes the entire instruction string, then starts over from the beginning, repeating the same instructions infinitely many times.

The goal is to return true if the robot's movement stays inside some circle forever. Otherwise, return false.

The key detail is that the robot does not stop after one pass through the instruction string. We must reason about its long term behavior after infinitely many repetitions.

The constraints are small:

  • 1 <= instructions.length <= 100
  • Each character is one of 'G', 'L', or 'R'

Since the input size is tiny, performance is not the main challenge. The real challenge is recognizing the mathematical pattern behind the robot's movement.

Several edge cases are important:

  • The robot may return to the origin after one cycle.
  • The robot may not return to the origin, but may end facing a different direction.
  • The robot may continue moving forever in a straight line.
  • The instruction string may contain only turns and no movement.
  • The instruction string may contain only forward moves.

A naive implementation might try to simulate infinitely many repetitions, which is obviously impossible. The solution depends on identifying when the motion becomes cyclic.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly simulate the robot for many cycles and track its positions. If the robot eventually revisits a previous state, we could conclude that its movement is cyclic and therefore bounded.

A state consists of:

  • The robot's x-coordinate
  • The robot's y-coordinate
  • The robot's current direction

If the same state appears again, the future movement pattern will repeat forever.

This approach is correct because robot movement is deterministic. Once a state repeats, the robot enters a loop.

However, this approach is inefficient and unnecessary. In the worst case, we may need to simulate many repetitions before discovering whether the movement is bounded. More importantly, there is a much simpler observation that completely characterizes the answer after only one execution of the instruction string.

Key Insight

The crucial observation is this:

After executing the instruction string once, the robot is bounded if either:

  1. The robot returns to the origin.
  2. The robot does not face north anymore.

Why does the second condition work?

If the robot changes direction after one cycle, then repeating the instructions rotates its trajectory. Since there are only four possible directions, the robot will eventually loop back toward the origin and remain within a bounded area.

On the other hand, if the robot ends somewhere other than the origin and still faces north, then the next repetition produces the exact same displacement again. The robot keeps drifting farther away forever in a straight pattern, so it is unbounded.

This means we only need to simulate the instruction string once.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(k × n) O(k) Simulates many repetitions and tracks visited states
Optimal O(n) O(1) One simulation is enough because of directional symmetry

Algorithm Walkthrough

Optimal Algorithm

  1. Initialize the robot's position and direction.

Start with:

  • x = 0
  • y = 0
  • facing north

We encode directions as integers:

  • 0 = north
  • 1 = east
  • 2 = south
  • 3 = west

This representation makes rotations easy using modular arithmetic. 2. Create a direction movement table.

We map each direction to its (dx, dy) movement:

  • north → (0, 1)
  • east → (1, 0)
  • south → (0, -1)
  • west → (-1, 0)
  1. Process each instruction one by one.

For every character in instructions:

  • If the instruction is 'G', move one step using the current direction vector.
  • If the instruction is 'L', rotate left by subtracting one direction index modulo 4.
  • If the instruction is 'R', rotate right by adding one direction index modulo 4.
  1. Examine the final state after one complete cycle.

After processing the full instruction string:

  • If the robot returned to (0, 0), return True.
  • Otherwise, if the robot is not facing north, return True.
  • Otherwise, return False.

Why it works

The important invariant is that repeating the same instruction sequence while facing different directions causes the displacement vector to rotate as well.

If the robot faces north again after one cycle and is not at the origin, the displacement repeats identically forever, causing the robot to drift infinitely far away.

If the robot faces a different direction, the displacement rotates every cycle. After at most four repetitions, the directional changes cancel out, forcing the robot into a bounded loop.

Python Solution

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        # Directions:
        # 0 = north
        # 1 = east
        # 2 = south
        # 3 = west
        
        directions = [
            (0, 1),   # north
            (1, 0),   # east
            (0, -1),  # south
            (-1, 0)   # west
        ]
        
        x, y = 0, 0
        direction = 0
        
        for instruction in instructions:
            if instruction == 'G':
                dx, dy = directions[direction]
                x += dx
                y += dy
            elif instruction == 'L':
                direction = (direction - 1) % 4
            else:  # instruction == 'R'
                direction = (direction + 1) % 4
        
        return (x == 0 and y == 0) or direction != 0

The implementation closely follows the algorithm described earlier.

The directions array stores movement vectors for each orientation. Instead of using string comparisons like "north" or "east", we use integer indices because turning left or right becomes simple modular arithmetic.

The variables x and y track the robot's current position. The variable direction stores the current orientation.

When processing a 'G' instruction, the code retrieves the movement vector corresponding to the current direction and updates the coordinates.

For rotations:

  • Turning left subtracts one direction index.
  • Turning right adds one direction index.

Using modulo 4 ensures the direction wraps correctly between 0 and 3.

After processing all instructions once, the final return statement implements the key mathematical observation:

  • Returning to the origin means the path is cyclic.
  • Ending with a different direction means future repetitions rotate the motion and keep the robot bounded.

Go Solution

func isRobotBounded(instructions string) bool {
    directions := [][]int{
        {0, 1},   // north
        {1, 0},   // east
        {0, -1},  // south
        {-1, 0},  // west
    }

    x, y := 0, 0
    direction := 0

    for _, instruction := range instructions {
        if instruction == 'G' {
            x += directions[direction][0]
            y += directions[direction][1]
        } else if instruction == 'L' {
            direction = (direction + 3) % 4
        } else {
            direction = (direction + 1) % 4
        }
    }

    return (x == 0 && y == 0) || direction != 0
}

The Go implementation is nearly identical to the Python version.

One small difference is how left rotation is handled. Instead of using negative modulo arithmetic, which can behave differently in Go, we add 3 modulo 4. This is mathematically equivalent to subtracting 1 modulo 4.

The direction vectors are stored as a slice of integer slices. Since coordinates remain small, integer overflow is not a concern.

Worked Examples

Example 1

Input:

instructions = "GGLLGG"

Initial state:

Step Instruction Position Direction
Start - (0, 0) North

Process instructions:

Step Instruction Position Direction
1 G (0, 1) North
2 G (0, 2) North
3 L (0, 2) West
4 L (0, 2) South
5 G (0, 1) South
6 G (0, 0) South

Final state:

  • Position = (0, 0)
  • Direction = South

Since the robot returned to the origin, the answer is true.

Example 2

Input:

instructions = "GG"

Initial state:

Step Instruction Position Direction
Start - (0, 0) North

Process instructions:

Step Instruction Position Direction
1 G (0, 1) North
2 G (0, 2) North

Final state:

  • Position = (0, 2)
  • Direction = North

The robot neither returned to the origin nor changed direction. Repeating the instructions keeps moving farther north forever.

Answer: false.

Example 3

Input:

instructions = "GL"

Initial state:

Step Instruction Position Direction
Start - (0, 0) North

Process instructions:

Step Instruction Position Direction
1 G (0, 1) North
2 L (0, 1) West

Final state:

  • Position = (0, 1)
  • Direction = West

The robot changed direction, so repeated cycles rotate its path and keep it bounded.

Answer: true.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We process each instruction exactly once
Space O(1) Only a few integer variables are used

The algorithm scans the instruction string one time, so the running time is linear in the length of the input.

The memory usage is constant because we store only the robot's coordinates, current direction, and a fixed direction table of size four.

Test Cases

solution = Solution()

# Provided examples
assert solution.isRobotBounded("GGLLGG") == True   # Returns to origin
assert solution.isRobotBounded("GG") == False      # Moves infinitely north
assert solution.isRobotBounded("GL") == True       # Changes direction

# Single instruction cases
assert solution.isRobotBounded("G") == False       # Moves forward forever
assert solution.isRobotBounded("L") == True        # Spins in place
assert solution.isRobotBounded("R") == True        # Spins in place

# Direction change without origin return
assert solution.isRobotBounded("GR") == True       # Ends facing east

# Full rotation back to north
assert solution.isRobotBounded("GLGLGLG") == True  # Forms a square

# Complex bounded movement
assert solution.isRobotBounded("GLRLLGLL") == True # Ends with changed direction

# Complex unbounded movement
assert solution.isRobotBounded("GGRRGG") == True   # Returns to origin

# Only turns
assert solution.isRobotBounded("LLLL") == True     # No movement

# Alternating turns and movement
assert solution.isRobotBounded("GLGLGGLGL") == True # Cyclic path

# Long straight movement
assert solution.isRobotBounded("GGGGGG") == False  # Infinite straight motion

Test Case Summary

Test Why
"GGLLGG" Validates returning to origin
"GG" Validates unbounded straight movement
"GL" Validates bounded motion via direction change
"G" Smallest unbounded movement case
"L" Rotation without movement
"R" Rotation without movement
"GR" Ends facing non-north direction
"GLGLGLG" Forms a closed square path
"GLRLLGLL" Complex turning behavior
"GGRRGG" Returns to origin after reversing
"LLLL" Multiple rotations only
"GLGLGGLGL" Nontrivial cyclic trajectory
"GGGGGG" Long straight-line drift

Edge Cases

Edge Case 1: The robot only turns

An instruction string like "LLLL" or "RR" causes the robot to rotate without ever moving. A buggy implementation might incorrectly assume that no movement means no cycle detection is needed.

Our implementation handles this naturally because the robot remains at (0, 0). The final condition immediately returns True.

Edge Case 2: The robot moves but changes direction

A sequence like "GL" does not return the robot to the origin after one cycle. A naive solution might incorrectly conclude that the robot is unbounded because its position changed.

However, the final direction is west instead of north. Repeating the instructions rotates the trajectory, eventually creating a loop. Our implementation correctly checks the direction as well as the position.

Edge Case 3: The robot keeps facing north

An instruction string like "GG" is the critical unbounded case. The robot moves away from the origin and still faces north after one cycle.

This means every future repetition adds the same displacement vector again and again. The robot drifts infinitely far away.

Our implementation detects this because:

  • (x, y) is not (0, 0)
  • direction == 0 meaning north

Therefore the function correctly returns False.