LeetCode 1041: Robot Bounded In Circle

Problem Restatement

A robot starts at the origin facing north and follows a sequence of instructions:

• 'G': move one step forward.
• 'L': turn left 90 degrees.
• 'R': turn right 90 degrees.

We need to determine if the robot stays within a bounded circle (i.e., the robot’s path is bounded) when the instructions are repeated indefinitely.

The official constraints state that 1 <= instructions.length <= 100.

Input and Output

Function shape:

def isRobotBounded(instructions: str) -> bool:
    ...

Examples

Example 1:

instructions = "GGLLGG"

After one cycle: the robot returns to the origin facing north. Bounded.

Answer: True.

Example 2:

instructions = "GG"

After one cycle: robot is 2 steps north, still facing north. Will drift infinitely north. Unbounded.

Answer: False.

Example 3:

instructions = "GL"

After one cycle: robot is at (0, 1) facing west (turned left once). After 4 cycles it returns to origin. Bounded.

Answer: True.

Key Insight

After one instruction cycle:

• If the robot is at the origin: bounded (it will loop back).
• If the robot is NOT facing north: bounded (it will spiral back — after 4 cycles at most, it returns to origin).
• If the robot is at a non-origin position and facing north: unbounded (it will drift infinitely in that direction).

Correctness

If the robot ends a cycle facing east/west, two cycles bring it back (net displacement is zero). If facing south, two cycles also bring it back. Only if facing north with a non-zero displacement does it drift.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # N, E, S, W
        x, y, d = 0, 0, 0

        for instr in instructions:
            if instr == 'G':
                x += dirs[d][0]
                y += dirs[d][1]
            elif instr == 'L':
                d = (d - 1) % 4
            else:
                d = (d + 1) % 4

        return (x == 0 and y == 0) or d != 0

Testing

def run_tests():
    s = Solution()

    assert s.isRobotBounded("GGLLGG") == True
    assert s.isRobotBounded("GG") == False
    assert s.isRobotBounded("GL") == True
    assert s.isRobotBounded("GLGLGGLGL") == True

    print("all tests passed")

run_tests()