Sponsored
Sponsored
The idea is to simulate the movement of the robot step by step according to the given instructions. We maintain the robot's current position and direction. If after one set of instructions, the robot has not returned to its original position but is not facing north, it must eventually form a circle upon repeated execution of the instructions.
Steps include initializing the position and direction, iterating over the instructions to update the position and direction, and finally checking conditions for cycle existence.
Time Complexity: O(n), where n is the length of the instructions string, because we iterate through the instructions once.
Space Complexity: O(1), since we use constant extra space for variables.
1public class Solution {
2 public bool IsRobotBounded(string instructions) {
3 int x = 0, y = 0, direction = 0;
4 int[,] deltas = new int[,] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
5
6 foreach (char inst in instructions) {
7 if (inst == 'G') {
8 x += deltas[direction, 0];
9 y += deltas[direction, 1];
10 } else if (inst == 'L') {
11 direction = (direction + 3) % 4;
12 } else if (inst == 'R') {
13 direction = (direction + 1) % 4;
14 }
15 }
16
17 return (x == 0 && y == 0) || direction != 0;
18 }
19}The C# version uses an integer array to define direction changes. During iteration, position updates with the array's help, and direction modifies through modulo operations. A check afterward confirms the bounded circle.
Here, simulate the robot's actions on the plane for up to four cycles of the input instructions. The observation is that if the robot returns to the starting position or is not facing north, then it will ultimately confine within a bounded circle.
The simulation idea draws from rotational symmetry and periodicity principles in movement patterns over multiple instruction applications.
Time Complexity: O(4n) = O(n); we simulate up to four full instruction loops.
Space Complexity: O(1), as it only uses constant space independent of input size.
class Solution {
public:
bool isRobotBounded(std::string instructions) {
int x = 0, y = 0, direction = 0;
int deltas[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int SIZE = 4;
for (int cycle = 0; cycle < SIZE; cycle++) {
for (char inst : instructions) {
if (inst == 'G') {
x += deltas[direction][0];
y += deltas[direction][1];
} else if (inst == 'L') {
direction = (direction + 3) % 4;
} else if (inst == 'R') {
direction = (direction + 1) % 4;
}
}
if (x == 0 && y == 0) return true;
}
return direction != 0;
}
};In C++, a four-cycle maximization ensures the symmetry and periodicity findings. Position checks per major cycle reinforce the condition for returning or alternate direction states.