1041. Robot Bounded In Circle

MediumMathStringSimulation
Leetcode Link

Problem Description

The problem involves a robot that operates on an infinite plane and can only make a limited set of movements. It starts at the coordinates (0, 0) and faces north. The robot can:

  • Move forward one unit ('G').
  • Make a 90-degree left turn ('L').
  • Make a 90-degree right turn ('R').

The robot repeats a sequence of these instructions infinitely. The main question is to determine whether the robot's movements are bounded within a circle - meaning that no matter how many times it repeats the instructions, it will never venture infinitely far away from the starting point.

Intuition

To solve this problem, the intuition lies in recognizing the pattern of the robot's movement after it completes the sequence of instructions once. If the robot returns to the (0, 0) point facing north, it will repeat the path exactly and is thus bounded within a circle.

However, if the robot does not return to the (0, 0) point but ends facing north, it will move further away with each repetition. Thus, it's not bounded by a circle.

If it ends up in any direction other than north, we know that after a maximum of 4 sequences, it will be back facing north (since there are 4 possible directions and a turn changes the direction by one). By this time, if it has not returned to the starting point, the path it takes would form a loop that repeats, hence it is bounded.

The solution code creates a direction variable k that indicates the current facing direction of the robot and an array dist that keeps the net distance moved in each direction (north, east, south, and west). After processing each instruction, there are two possible cases that define if the robot is bounded:

  1. dist[0] == dist[2] and dist[1] == dist[3]: This means the net distance moved north equals the net distance moved south, and the net distance moved east equals the net distance moved west, indicating it's back at the starting point facing north.
  2. k != 0: This indicates that the robot is facing a different direction than it started with, after completing the sequence. Hence, in this case, it's guaranteed to be bounded by a circle after enough repetitions.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Solution Approach

The implementation of the solution involves a step-by-step process to determine the robot's status after executing one sequence of instructions:

  1. Initialize Direction and Distance: A variable k is set to 0, representing the robot's direction (0 for north, 1 for east, 2 for south, 3 for west), and a list dist is initialized with four zeros to track the net distance moved in each of the four directions.

  2. Process Instructions: The function iterates through each character in the instructions string:

    • If it encounters 'L', it turns the robot left by incrementing k and then taking modulo 4. This ensures k remains in the range [0, 3].
    • If it encounters 'R', it turns the robot right by decrementing k (add 3 before modulo to simulate the rotation right), then taking modulo 4.
    • If it encounters 'G', it increments the distance by 1 in the direction the robot is currently facing, which is updated in the dist list.

  3. Check for Boundedness: After processing all instructions, the robot's boundedness is determined using two checks:

    • dist[0] == dist[2] and dist[1] == dist[3]: This check compares the net north-south and east-west movements. If these are equal, it means the robot has returned to the initial point (0, 0) and is therefore bounded.
    • k != 0: This check sees if the robot is facing a different direction than the initial one. If it is not facing north, it implies the robot is on a path that will repeat and form a loop, hence it is bounded.

By using an array to track the net movement in each cardinal direction and a variable for direction, the solution leverages simple mathematical properties and modular arithmetic to determine the robot's path characteristics in an efficient manner. This approach ensures that we are only concerned with the state of the robot after one sequence, greatly simplifying the problem which otherwise might seem to require simulating an infinite number of instruction sequences.

In short, the solution leverages the following algorithms and data structures:

  • A loop to iterate over the instructions.
  • An array to maintain net distances in four cardinal directions.
  • Modular arithmetic for direction updates ensuring the direction stays within bounds.
  • Conditional logic to assert the robot's boundedness.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider that the instructions string given to our robot is "GGLLGG".

  1. Initialize Direction and Distance: Let's initialize the robot's direction k to 0 (facing north) and the list dist to [0, 0, 0, 0], tracking the net distance moved in each cardinal direction: north, east, south, and west, respectively.

  2. Process Instructions:

    • First, the robot sees 'G' and moves forward one unit north. The dist list becomes [1, 0, 0, 0].
    • Then, another 'G' means it moves one more unit north. The dist list is now [2, 0, 0, 0].
    • Next, the instruction 'L' tells the robot to turn left (west), so we increment k by 1 and take modulo 4, giving us k = 1.
    • Another 'L' instruction turns the robot left from west to south, updating k to 2 after incrementation and modulo.
    • The robot encounters 'G', moving one unit south. The dist array updates to [2, 0, 1, 0].
    • The final 'G' means another move south, resulting in dist being [2, 0, 2, 0].

  3. Check for Boundedness:

    • We check if dist[0] == dist[2] and dist[1] == dist[3]. Indeed, 2 == 2 and 0 == 0, which means the robot has returned to the initial point (0, 0) facing south (k = 2).
    • We also check if k != 0. Since k is 2, it indeed is not equal to 0, which implies that the robot did not end facing north.

From the checks, we conclude that the robot does not keep moving away infinitely from the starting point. Even if the instructions are repeated infinitely, the robot will always return to (0, 0) after each set of instructions, creating a looped path. Thus, it is bounded within an invisible circle defined by its path.

Solution Implementation

1class Solution:
2    def isRobotBounded(self, instructions: str) -> bool:
3        # Initialize the direction index, 0 = North, 1 = West, 2 = South, 3 = East
4        direction_index = 0
5      
6        # Initialize distances for all four directions,
7        # index corresponds to the direction: 0 = North, 1 = West, 2 = South, 3 = East
8        distances = [0, 0, 0, 0]
9      
10        # Loop through each character in the instructions string
11        for command in instructions:
12            if command == 'L':
13                # Turn left: Update direction_index counter-clockwise
14                direction_index = (direction_index + 1) % 4
15            elif command == 'R':
16                # Turn right: Update direction_index clockwise
17                direction_index = (direction_index + 3) % 4
18            else:  # command == 'G'
19                # Move forward: Increment distance in the current facing direction
20                distances[direction_index] += 1
21      
22        # Check if the robot returns to the original position (circular) OR
23        # is facing in a different direction other than North after one cycle of instructions
24        # This ensures that repeating the instructions will eventually bring it back to the origin.
25        is_circular = (distances[0] == distances[2] and distances[1] == distances[3]) or direction_index != 0
26      
27        return is_circular
28
1class Solution {
2    public boolean isRobotBounded(String instructions) {
3        // 'directionIndex' represents the current direction of the robot:
4        // 0-Up, 1-Left, 2-Down, 3-Right
5        int directionIndex = 0;
6
7        // 'distance' array stores the net distance moved in all 4 directions.
8        int[] distance = new int[4];
9
10        // Iterate over each instruction and update the direction or distance accordingly.
11        for (int i = 0; i < instructions.length(); ++i) {
12            char currentInstruction = instructions.charAt(i);
13
14            // If the instruction is 'L', it turns the robot 90 degrees to the left.
15            if (currentInstruction == 'L') {
16                directionIndex = (directionIndex + 1) % 4;
17            } 
18            // If the instruction is 'R', it turns the robot 90 degrees to the right.
19            else if (currentInstruction == 'R') {
20                directionIndex = (directionIndex + 3) % 4;
21            } 
22            // If the instruction is 'G', the robot moves forward one unit in the current direction.
23            else {
24                distance[directionIndex]++;
25            }
26        }
27
28        // The robot is bounded if:
29        // 1. It returns to the initial position (distance moved up equals down and left equals right).
30        // 2. It is not facing north after processing all instructions.
31        return (distance[0] == distance[2] && distance[1] == distance[3]) || (directionIndex != 0);
32    }
33}
34
1class Solution {
2public:
3    // Function to determine if the robot is bounded in a circle.
4    bool isRobotBounded(string instructions) {
5        // Define an array to store the distance moved in each of the four directions (North, East, South, West).
6        int distances[4] = {0};
7        // 'direction' represents the current direction of the robot: 0 - North, 1 - East, 2 - South, 3 - West.
8        int direction = 0;
9      
10        // Iterate over the given instruction string.
11        for (char& instruction : instructions) {
12            // Change direction based on the current instruction.
13            if (instruction == 'L') {
14                direction = (direction + 1) % 4; // Turning left.
15            } else if (instruction == 'R') {
16                direction = (direction + 3) % 4; // Turning right.
17            } else { // 'instruction' must be 'G' at this point, which means go straight.
18                // Increment the distance in the current direction.
19                ++distances[direction];
20            }
21        }
22      
23        // The robot is bounded in a circle if it returns to the origin,
24        // or if it doesn't face north at the end of the sequence.
25        // Returning to the origin means having the same number of moves in opposite directions.
26        return (distances[0] == distances[2] && distances[1] == distances[3]) || direction != 0;
27    }
28};
29
1function isRobotBounded(instructions: string): boolean {
2    // Array to keep track of distance moved in 4 directions: 
3    // north (index 0), east (index 1), south (index 2), and west (index 3).
4    const distances: number[] = new Array(4).fill(0);
5  
6    // Variable 'direction' to keep track of current direction:
7    // 0 = north, 1 = east, 2 = south, 3 = west.
8    let direction = 0;
9  
10    // Loop through each instruction character
11    for (const instruction of instructions) {
12        if (instruction === 'L') {
13            // Turn left from current direction
14            direction = (direction + 1) % 4;
15        } else if (instruction === 'R') {
16            // Turn right from current direction (3 left turns)
17            direction = (direction + 3) % 4;
18        } else {
19            // Move one unit in the current direction
20            ++distances[direction];
21        }
22    }
23
24    // Check if robot is back to the original position (x = 0 and y = 0)
25    // or it is not facing north. Facing not north means the loop will return to the origin
26    // in another one or more sequences of instructions.
27    return (distances[0] === distances[2] && distances[1] === distances[3]) || direction !== 0;
28}
29
Not Sure What to Study? Take the 2-min Quiz：

Depth first search can be used to find whether two components in a graph are connected.

Time and Space Complexity

The code snippet presented is designed to determine if a set of instructions will cause a robot to end up in a circle or not. Here is the complexity analysis:

Time Complexity

The time complexity of the algorithm is determined by the number of instructions that need to be processed. The for-loop iterates through each character in the instructions string once.

  • The for-loop runs for n iterations, where n is the length of the instructions.
  • Each operation within the for-loop (checking the character and updating k or dist) is a constant time operation.
  • Therefore, the time complexity is O(n), where n is the length of the instructions string.

Space Complexity

The space complexity of the algorithm is determined by the amount of extra space used irrespective of the input size.

  • A fixed-size list dist of 4 integers is used to keep track of the distances moved in each of the four directions.
  • Variable k is used to keep track of the current direction, which also uses a constant amount of space.
  • As there is no dynamic data structure that grows with the input size and only a fixed amount of extra space is used, the space complexity is O(1), which means it is constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫