Robot Bounded In Circle

Medium Arrays & Hashing Simulation Original on LeetCode

Reported atAirbnb

Robot Bounded In Circle is a medium arrays & hashing problem solved with the simulation pattern. The best approach, optimal (one run, check position and heading), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from simulate four runs up.

Problem

A robot stands at the origin (0, 0) of an infinite grid, facing north. It understands three commands: 'G' moves one unit forward, 'L' turns 90 degrees left and 'R' turns 90 degrees right, both without moving.

The robot executes the string instructions and then starts over from the beginning, repeating it forever. Return true if the robot always stays inside some fixed circle around the origin, and false if it wanders off without limit.

Examples

Example 1

Input
instructions = "GRGRGRG"
Output
true
Why
The robot walks the four sides of a 1 × 1 square and is back at the origin after one run.

Example 2

Input
instructions = "GGR"
Output
true
Why
After one run it stands at (0, 2) facing east. Four runs trace a square and bring it home.

Example 3

Input
instructions = "GLGR"
Output
false
Why
Each run ends one step further up and one step left, still facing north, so it drifts away forever.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Simulate four runsO(n)O(1)
Optimal (one run, check position and heading)O(n)O(1)

1Simulate four runs

TimeO(n)Four passes over the n instructions.
SpaceO(1)Only the position and the heading.

Every run rotates the robot's heading by the same amount, so after four runs the total turn is a multiple of 360 degrees. Then the four displacement vectors cancel unless the heading never changed and the robot moved. So just simulate four full runs and check whether the robot is back at the origin.

  1. Start at (0, 0) facing north; directions are north, east, south, west in clockwise order.
  2. Repeat 4 times: for each character, G moves one step in the current direction, L turns to (d + 3) % 4, R turns to (d + 1) % 4.
  3. Return true if the robot is at (0, 0).
class Solution {
    public boolean isRobotBounded(String instructions) {
        int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int x = 0, y = 0, d = 0;
        for (int rep = 0; rep < 4; rep++) {
            for (char c : instructions.toCharArray()) {
                if (c == 'G') {
                    x += dirs[d][0];
                    y += dirs[d][1];
                } else if (c == 'L') {
                    d = (d + 3) % 4;
                } else {
                    d = (d + 1) % 4;
                }
            }
        }
        return x == 0 && y == 0;
    }
}

2Optimal (one run, check position and heading)

TimeO(n)One pass over the instructions.
SpaceO(1)Only the position and the heading.

Simulate a single run. If the robot is back at the origin it obviously loops. If it is somewhere else but no longer faces north, its next runs are the same displacement rotated, and two or four runs bring it back. Only a robot that moved and still faces north escapes.

  1. Simulate the instructions once from (0, 0) facing north.
  2. Return true if (x, y) == (0, 0) or the final heading is not north.
class Solution {
    public boolean isRobotBounded(String instructions) {
        int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int x = 0, y = 0, d = 0;
        for (char c : instructions.toCharArray()) {
            if (c == 'G') {
                x += dirs[d][0];
                y += dirs[d][1];
            } else if (c == 'L') {
                d = (d + 3) % 4;
            } else {
                d = (d + 1) % 4;
            }
        }
        return (x == 0 && y == 0) || d != 0;
    }
}

Edge cases to test

  • Only turns and no moves, like "LR" or "L"
  • Only moves, like "GGG", which drifts north forever
  • A run that ends away from the origin but facing a new direction

Hints

Hint 1

Look at where the robot is and which way it faces after one full run of the instructions.

Hint 2

If it ends facing a different direction, what happens after four runs?

Hint 3

The path is bounded exactly when the robot is back at the origin, or no longer faces north, after one run.

FAQ

What is the best time complexity for Robot Bounded In Circle?

Optimal (one run, check position and heading) runs in O(n) time and O(1) extra space. One pass over the instructions.

Which pattern does Robot Bounded In Circle use?

It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, Integer to English Words, String to Integer (atoi).

Is there a brute force solution for Robot Bounded In Circle?

Yes. Simulate four runs takes O(n) time and O(1) space. Every run rotates the robot's heading by the same amount, so after four runs the total turn is a multiple of 360 degrees.

Which edge cases should I test for Robot Bounded In Circle?

Only turns and no moves, like "LR" or "L"; Only moves, like "GGG", which drifts north forever; A run that ends away from the origin but facing a new direction.