⚡Flashcard Drill➔
NeetCode #920LC-1041MediumMath & Geometry
← Back to All Problems

#920 · #1041 · Robot Bounded In Circle(困于环中的机器人)

📌 Problem Statement & Constraints

A robot starts at (0, 0) facing north on an infinite plane and executes a list of instructions repeatedly forever: G moves forward one unit, L turns left 90 degrees, and R turns right 90 degrees. Return true if there exists a circle in the plane that the robot never leaves. Constraints: 1 <= instructions.length <= 100, and the string contains only G, L and R.

💡 Core Algorithmic Approaches

  1. Execute the instruction string once and record the resulting displacement (x, y) and heading d.
  2. If the robot returns to the origin, it is trivially bounded, since each repetition retraces the same path.
  3. If its heading changed (it no longer faces north), the repeated runs trace a closed polygon, so the robot is also bounded.
  4. If it moved away from the origin and still faces north, each repetition translates the whole path outward, so the robot escapes to infinity.

💻 Benchmark Python3 Implementation

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        # directions: north, east, south, west
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        x = y = 0
        d = 0
        for ch in instructions:
            if ch == "G":
                x += dirs[d][0]
                y += dirs[d][1]
            elif ch == "L":
                d = (d + 3) % 4        # turn left
            else:                      # ch == "R"
                d = (d + 1) % 4        # turn right
        return (x == 0 and y == 0) or d != 0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single simulation pass.
💾 Space Complexity
O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Only checking whether the robot returned to the origin: a bounded robot need not return to the origin after one pass, as long as its heading changed.
  • Simulating many repetitions: the state after one pass already decides the answer.
  • Swapping L and R: turning left is d - 1 (equivalently +3) and turning right is d + 1, both modulo 4.
  • Testing d != 0 alone: a robot that ends north but at the origin is bounded, so the origin check must be part of the disjunction.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems