Robot Bounded In Circle - Practice Coding Problems

Robot Bounded In Circle - Problem

On an infinite plane, a robot initially stands at (0, 0) and faces north.

Note that:

The north direction is the positive direction of the y-axis.
The south direction is the negative direction of the y-axis.
The east direction is the positive direction of the x-axis.
The west direction is the negative direction of the x-axis.

The robot can receive one of three instructions:

"G": go straight 1 unit.
"L": turn 90 degrees to the left (i.e., anti-clockwise direction).
"R": turn 90 degrees to the right (i.e., clockwise direction).

The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Input & Output

Example 1 — Returns to Origin

$ Input: instructions = "GGLLGG"

› Output: true

💡 Note: After executing once: robot moves north 2 units, turns left twice (now facing south), moves south 2 units, ending at origin (0,0). Since it's back at the starting position, it will repeat the same path forever.

Example 2 — Different Direction

$ Input: instructions = "GG"

› Output: false

💡 Note: After executing once: robot moves north 2 units to position (0,2) and still faces north. It will keep moving north indefinitely, so it's unbounded.

Example 3 — Turns Only

$ Input: instructions = "GL"

› Output: true

💡 Note: After executing once: robot moves north 1 unit to (0,1) then turns left to face west. Since it's not facing north anymore, it will eventually return to origin after 4 cycles.

Constraints

1 ≤ instructions.length ≤ 100
instructions[i] is 'G', 'L' or 'R'

Visualization

Tap to expand

Understanding the Visualization

Input

Instruction string like "GGLLGG"

Simulate

Execute instructions once, track position and direction

Check

Bounded if at origin OR not facing north

Key Takeaway

🎯 Key Insight: Check position and direction after one cycle - if at origin OR not facing north, robot is bounded

Asked in

G Google 25 a Amazon 18 M Microsoft 15 🍎 Apple 12

The key insight is that after executing instructions once, the robot is bounded if it's either back at origin OR facing a different direction. The mathematical solution runs in O(n) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Analysis	O(n)	O(1)	Use mathematical properties to determine boundedness in O(n) time
Multiple Cycle Simulation	O(n)	O(1)	Simulate multiple cycles until position repeats or exceeds bounds

Mathematical Analysis — Algorithm Steps

Execute instructions once to get final position and direction
Check if robot is at origin (repeats same path)
Check if robot faces different direction (will eventually return)
Return true if either condition is met

Visualization

Tap to expand

Step-by-Step Walkthrough

Execute Once

Run instruction sequence once

Check Conditions

At origin? Or facing different direction?

Mathematical Proof

Either condition guarantees boundedness

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* instructions) {
    // Direction vectors: North, East, South, West
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};
    int x = 0, y = 0;
    int facing = 0;  // 0=North, 1=East, 2=South, 3=West
    
    for (int i = 0; instructions[i]; i++) {
        if (instructions[i] == 'G') {
            x += dx[facing];
            y += dy[facing];
        } else if (instructions[i] == 'L') {
            facing = (facing - 1 + 4) % 4;
        } else {  // instructions[i] == 'R'
            facing = (facing + 1) % 4;
        }
    }
    
    // Bounded if: back at origin OR not facing North
    return (x == 0 && y == 0) || facing != 0;
}

int main() {
    char instructions[10001];
    fgets(instructions, sizeof(instructions), stdin);
    instructions[strcspn(instructions, "\n")] = 0;
    
    bool result = solution(instructions);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all instructions

✓ Linear Growth

Space Complexity

O(1)

Only storing position and direction variables

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler