We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Robot Bounded In Circle

Number: 1119

Difficulty: Medium

Paid? No

Companies: Goldman Sachs, Apple, Amazon, ZScaler, LinkedIn, Chewy, Bloomberg, Rivian, Airbnb

Problem Description

Determine whether a sequence of movement instructions for a robot will keep it within a circle on an infinite plane. The robot starts at (0, 0) facing north and repeats the given instruction string forever. Instructions include moving forward ("G"), turning left ("L"), and turning right ("R"). The goal is to check if the robot’s path is cyclic (bounded in a circle).

Key Insights

  • If after one cycle of instructions the robot returns to the origin, it is bounded.
  • If the robot does not face north after one cycle (even if not at the origin), its trajectory will eventually loop.
  • Simulate the robot's movement using directional vectors representing north, east, south, and west.
  • The problem can be solved with O(n) time complexity given the fixed instruction length and O(1) space.

Space and Time Complexity

Time Complexity: O(n) per cycle, where n is the length of the instructions.
Space Complexity: O(1) since only fixed extra space is used.

Solution

We simulate the robot's movement based on the instructions and track its position and current direction using a direction index mapped to directional vectors (north, east, south, west). After executing the instruction sequence once, if the robot is back at the origin or its direction is not north, then the robot's path will eventually loop within a circle. The key insight is that a change in direction implies that the repeated sequences will cause the robot to move in a cyclical pattern.

Code Solutions

# Python solution with detailed comments

def isRobotBounded(instructions: str) -> bool:
    # Define initial position (x, y) and start facing north
    x, y = 0, 0
    # Directions represented as vectors in order: north, east, south, west
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    # Start with direction index 0 (facing north)
    dir_index = 0

    # Process each instruction character
    for char in instructions:
        if char == 'G':  # Move forward in current direction
            dx, dy = directions[dir_index]
            x += dx
            y += dy
        elif char == 'L':  # Turn left: decrement direction index (with wrap-around)
            dir_index = (dir_index - 1) % 4
        elif char == 'R':  # Turn right: increment direction index (with wrap-around)
            dir_index = (dir_index + 1) % 4

    # Check if robot returns to origin or is not facing north
    return (x == 0 and y == 0) or (dir_index != 0)

# Example usage:
print(isRobotBounded("GGLLGG"))  # Expected output: True
← Back to All Questions