Problem statement

A robot stands at the origin (0, 0) of an infinite grid, facing north (the direction of increasing y). It understands three instructions:

• 'G': move forward one unit;
• 'L': turn 90 degrees left (anticlockwise);
• 'R': turn 90 degrees right (clockwise).

The robot performs the string instructions in order, and then repeats it from the start, forever.

Return true if there is a circle on the plane that the robot never leaves, and false if it wanders off arbitrarily far.

Example 1

Input: instructions = "GGLLGG"
Output: true
Explanation: The robot walks to (0, 2), turns around and walks back to (0, 0): it stays inside a circle of radius 2.

Example 2

Input: instructions = "GG"
Output: false
Explanation: It moves north two units every round, forever.

Example 3

Input: instructions = "GL"
Output: true
Explanation: It traces the square (0,0) → (0,1) → (-1,1) → (-1,0) → (0,0) over four rounds.

Constraints

• 1 <= instructions.length <= 100
• instructions[i] is 'G', 'L' or 'R'

Hints for Robot Bounded In Circle

1. Hint 1

   Run the instructions once and look at where the robot ends and which way it faces.

2. Hint 2

   If it ends back at the origin, it repeats the same loop forever. If it ends somewhere else but still facing north, every round shifts it by the same vector.

3. Hint 3

   If it ends facing any other direction, after two or four rounds the displacements cancel out.

How to solve Robot Bounded In Circle

After one pass the robot is bounded exactly when it is back at the origin or no longer facing north.

Approach

1. Simulate one pass, keeping the position (x, y) and the direction as a unit vector (dx, dy) starting at (0, 1).
2. 'G' adds the direction to the position; 'L' turns (dx, dy) into (-dy, dx); 'R' turns it into (dy, -dx).
3. Return true if the position is (0, 0) or the direction is not (0, 1).

Why it works

One pass moves the robot by a displacement v and rotates it by some angle. If it faces north again, each pass adds the same v, so it stays bounded only if v = 0. If it turned by 180°, the second pass adds -v and the robot is home after two passes; if it turned by ±90°, the four passes add v rotated four ways, which sum to zero. In those cases the path repeats with a finite period and fits in a circle.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Checking only 'back at the origin' misses "GL", which ends elsewhere but turns.
• Getting the rotation formulas mixed up: left from north must face west, i.e. (0, 1) → (-1, 0).
• Simulating many rounds to 'see' if it escapes is unnecessary — four rounds always settle it.

Reference solution

Python

def isRobotBounded(instructions: str) -> bool:
    x = y = 0
    dx, dy = 0, 1
    for c in instructions:
        if c == 'G':
            x += dx
            y += dy
        elif c == 'L':
            dx, dy = -dy, dx
        else:
            dx, dy = dy, -dx
    return (x == 0 and y == 0) or (dx, dy) != (0, 1)

Java

public static boolean isRobotBounded(String instructions) {
    int x = 0, y = 0, dx = 0, dy = 1;
    for (int i = 0; i < instructions.length(); i++) {
        char c = instructions.charAt(i);
        if (c == 'G') {
            x += dx;
            y += dy;
        } else if (c == 'L') {
            int t = dx; dx = -dy; dy = t;
        } else {
            int t = dx; dx = dy; dy = -t;
        }
    }
    return (x == 0 && y == 0) || !(dx == 0 && dy == 1);
}

C++

bool isRobotBounded(string instructions) {
    int x = 0, y = 0, dx = 0, dy = 1;
    for (char c : instructions) {
        if (c == 'G') {
            x += dx;
            y += dy;
        } else if (c == 'L') {
            int t = dx; dx = -dy; dy = t;
        } else {
            int t = dx; dx = dy; dy = -t;
        }
    }
    return (x == 0 && y == 0) || !(dx == 0 && dy == 1);
}

JavaScript

var isRobotBounded = function(instructions) {
    var x = 0, y = 0, dx = 0, dy = 1;
    for (var i = 0; i < instructions.length; i++) {
        var c = instructions[i], t;
        if (c === 'G') {
            x += dx;
            y += dy;
        } else if (c === 'L') {
            t = dx; dx = -dy; dy = t;
        } else {
            t = dx; dx = dy; dy = -t;
        }
    }
    return (x === 0 && y === 0) || !(dx === 0 && dy === 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Product of the Last K Numbers Medium
• Add 1 to a Number Represented as Linked List Medium
• Double a Number Represented as a Linked List Medium
• Insert Greatest Common Divisors in Linked List Medium
• Add Two Numbers II Medium
• Add Two Numbers Medium