Problem Description

You have a robot on an infinite 2D plane that starts at position (0, 0) facing north. The coordinate system is defined as:

• North: positive y-axis direction
• South: negative y-axis direction
• East: positive x-axis direction
• West: negative x-axis direction

The robot can execute three types of instructions:

• "G": Move forward 1 unit in the current direction
• "L": Turn 90 degrees left (counter-clockwise)
• "R": Turn 90 degrees right (clockwise)

Given a string instructions containing these commands, the robot will execute the entire instruction sequence and then repeat it infinitely.

Your task is to determine if the robot will stay within a bounded circle on the plane. Return true if the robot's path is bounded (never leaves some circle), and false otherwise.

For example:

• If instructions = "GGLLGG", the robot moves forward 2 units, turns left twice (facing south), then moves forward 2 units. After one cycle, it returns to (0, 0) facing south. Since it returns to origin, it will stay bounded.
• If instructions = "GG", the robot keeps moving north indefinitely, so it's not bounded.

The key insight is that after executing the instruction sequence once, if either:

1. The robot returns to the origin (0, 0), OR
2. The robot faces a different direction than north

Then the robot will stay within a bounded circle. This is because changing direction means the robot will eventually trace a closed path after multiple cycles (at most 4 cycles for a full rotation back to north).

Intuition

The key insight comes from observing what happens when we repeat the instruction sequence multiple times. Let's think about what determines whether the robot stays bounded:

After executing the instructions once, the robot ends up at some position (x, y) facing some direction. Now we need to understand when repeating this pattern keeps the robot bounded.

Case 1: Robot returns to origin after one cycle If after one execution the robot is back at (0, 0), then no matter which direction it faces, repeating the instructions will just keep bringing it back to origin. The robot traces a closed loop and stays bounded.

Case 2: Robot doesn't return to origin This is more interesting. The robot is at position (x, y) after one cycle. What happens next depends on which direction it's facing:

• Still facing North (same as start): The second execution will move the robot by another (x, y), third by another (x, y), and so on. The position after n cycles becomes (n*x, n*y). Since x or y is non-zero (not at origin), the robot keeps moving away infinitely - unbounded.

• Facing West (turned left once): After the second cycle, the displacement is (-y, x) relative to first cycle's end. After the third cycle, it's (-x, -y). After the fourth, it's (y, -x). Adding these up: (x, y) + (-y, x) + (-x, -y) + (y, -x) = (0, 0). The robot returns to origin after 4 cycles - bounded.

• Facing South (turned 180°): The second cycle moves the robot by (-x, -y). Combined with the first cycle's (x, y), we get back to (0, 0) after just 2 cycles - bounded.

• Facing East (turned right once): Similar to facing west, after 4 cycles the displacements cancel out and return to origin - bounded.

The pattern emerges: if the robot changes direction after one cycle, the different orientations cause the displacement vectors to eventually cancel out (after at most 4 cycles). But if it maintains the original direction, it keeps accumulating displacement in the same direction forever.

Therefore, we can determine boundedness by checking after one execution:

1. Did we return to origin? (distances cancel: dist[North] == dist[South] and dist[East] == dist[West])
2. OR did we change direction? (k != 0 where k represents the final direction)

If either condition is true, the robot stays bounded.

Learn more about Math patterns.

Solution Approach

The implementation uses a simulation approach to track the robot's movement through one complete execution of the instruction sequence.

Data Structures:

• k: An integer representing the robot's current direction (0=North, 1=West, 2=South, 3=East)
• dist: An array of size 4 to track the distance traveled in each direction

Algorithm Steps:

1. Initialize the tracking variables:

   • Set k = 0 (robot starts facing North)
   • Create dist = [0, 0, 0, 0] to track distances in each direction

2. Process each instruction: For each character c in the instruction string:

   • Left turn ('L'): Update direction by k = (k + 1) % 4
     • This rotates counter-clockwise through: North→West→South→East→North
   • Right turn ('R'): Update direction by k = (k + 3) % 4
     • Adding 3 is equivalent to subtracting 1 in modulo 4, rotating clockwise
     • This rotates through: North→East→South→West→North
   • Go forward ('G'): Increment the distance in current direction by dist[k] += 1

3. Check boundedness conditions: After processing all instructions, return true if either:

   • Robot returns to origin: dist[0] == dist[2] and dist[1] == dist[3]
     • dist[0] (North) equals dist[2] (South): net vertical displacement is 0
     • dist[1] (West) equals dist[3] (East): net horizontal displacement is 0
   • OR robot changed direction: k != 0
     • The robot is no longer facing North after one cycle

Why this works:

• If the robot moves North n times and South n times, the vertical movements cancel out
• If the robot moves East m times and West m times, the horizontal movements cancel out
• Together, these conditions check if the robot returns to (0, 0)
• If the robot doesn't return to origin but changed direction (k != 0), we know from our analysis that after at most 4 cycles, the displacement vectors will cancel out due to rotation

The elegance of this solution is that we don't need to simulate multiple cycles - just one execution tells us everything we need to determine boundedness.

Example Walkthrough

Let's trace through the example instructions = "GGLLGG" to see how our solution determines boundedness.

Initial State:

• Direction k = 0 (facing North)
• Distance array dist = [0, 0, 0, 0] representing [North, West, South, East]

Processing each instruction:

1. 'G' (1st): Move forward while facing North

   • dist[0] += 1 → dist = [1, 0, 0, 0]
   • Robot position: (0, 1)

2. 'G' (2nd): Move forward while still facing North

   • dist[0] += 1 → dist = [2, 0, 0, 0]
   • Robot position: (0, 2)

3. 'L' (3rd): Turn left

   • k = (0 + 1) % 4 = 1 (now facing West)
   • No position change

4. 'L' (4th): Turn left again

   • k = (1 + 1) % 4 = 2 (now facing South)
   • No position change

5. 'G' (5th): Move forward while facing South

   • dist[2] += 1 → dist = [2, 0, 1, 0]
   • Robot position: (0, 1)

6. 'G' (6th): Move forward while still facing South

   • dist[2] += 1 → dist = [2, 0, 2, 0]
   • Robot position: (0, 0)

Final Check:

• Final direction: k = 2 (facing South, not North)
• Final distances: dist = [2, 0, 2, 0]

Boundedness conditions:

1. Check if at origin:

   • dist[0] == dist[2]? → 2 == 2 ✓ (North and South distances equal)
   • dist[1] == dist[3]? → 0 == 0 ✓ (West and East distances equal)
   • Robot returned to origin!

2. Check if direction changed:

   • k != 0? → 2 != 0 ✓ (Also true - facing South, not North)

Since the robot returns to origin (condition 1 is satisfied), the function returns true. The robot will stay bounded, repeatedly tracing the same rectangular path: up 2, turn around, down 2, and back to start.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the instructions string exactly once. For each character in the string, it performs constant-time operations:

• Checking the character type ('L', 'R', or 'G')
• Updating the direction k with modulo operations
• Incrementing a distance counter

Since we process each of the n characters exactly once with O(1) operations per character, the overall time complexity is O(n), where n is the length of the instruction string.

Space Complexity: O(1)

The algorithm uses a fixed amount of extra space:

• Variable k to track the current direction (single integer)
• Array dist of fixed size 4 to track distances in each direction

The space usage does not depend on the input size n. The dist array always has exactly 4 elements regardless of how long the instructions string is. Therefore, the space complexity is O(1) (constant space).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Direction Mapping Leading to Wrong Distance Tracking

One of the most common mistakes is using an inconsistent or incorrect mapping between direction indices and actual compass directions. This leads to recording movements in the wrong direction slots.

Pitfall Example:

# Incorrect mapping where developers might use:
# 0=North, 1=East, 2=South, 3=West (clockwise order)
# But then use the wrong rotation logic

direction = 0  # North
distance = [0] * 4

for instruction in instructions:
    if instruction == 'L':
        direction = (direction + 1) % 4  # This would go North->East (wrong!)
    elif instruction == 'R':
        direction = (direction - 1) % 4  # This would go North->West (wrong!)
    else:
        distance[direction] += 1

Why it's wrong: The rotation logic doesn't match the direction mapping. If you use clockwise ordering (N→E→S→W), then turning left should decrease the index, not increase it.

Solution: Stick to one consistent mapping and ensure your rotation logic matches:

Option 1 - Counter-clockwise mapping (as in the original solution):

# 0=North, 1=West, 2=South, 3=East
# Left turn: (direction + 1) % 4
# Right turn: (direction + 3) % 4

Option 2 - Clockwise mapping:

# 0=North, 1=East, 2=South, 3=West
# Left turn: (direction + 3) % 4  # or (direction - 1 + 4) % 4
# Right turn: (direction + 1) % 4

2. Using Coordinate Tracking Instead of Direction-Based Distance

Another pitfall is trying to track the exact (x, y) position and getting confused with direction changes.

Pitfall Example:

def isRobotBounded(self, instructions: str) -> bool:
    x, y = 0, 0
    dx, dy = 0, 1  # Initially facing north
  
    for instruction in instructions:
        if instruction == 'L':
            # Incorrect rotation transformation
            dx, dy = dy, dx  # Wrong! This doesn't rotate 90 degrees
        elif instruction == 'R':
            dx, dy = -dy, dx  # May have signs wrong
        else:
            x += dx
            y += dy
  
    return (x == 0 and y == 0) or (dx != 0 or dy != 1)

Why it's wrong: The rotation transformations for (dx, dy) are easy to get wrong. The correct 90-degree rotations are:

• Left turn: (dx, dy) -> (-dy, dx)
• Right turn: (dx, dy) -> (dy, -dx)

Solution: If using coordinate approach, ensure correct rotation matrices:

def isRobotBounded(self, instructions: str) -> bool:
    x, y = 0, 0
    dx, dy = 0, 1  # Initially facing north
  
    for instruction in instructions:
        if instruction == 'L':
            dx, dy = -dy, dx  # Correct 90° counter-clockwise
        elif instruction == 'R':
            dx, dy = dy, -dx  # Correct 90° clockwise
        else:
            x += dx
            y += dy
  
    return (x == 0 and y == 0) or (dx != 0 or dy != 1)

3. Forgetting to Check Both Conditions for Boundedness

Pitfall Example:

def isRobotBounded(self, instructions: str) -> bool:
    # ... simulation code ...
  
    # Only checking if robot returns to origin
    return distance[0] == distance[2] and distance[1] == distance[3]
    # Forgot to check if direction changed!

Why it's wrong: The robot can be bounded even if it doesn't return to origin after one cycle, as long as it's facing a different direction. After at most 4 cycles, it will form a closed loop.

Solution: Always check both conditions:

return (distance[0] == distance[2] and distance[1] == distance[3]) or direction != 0