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
- Execute the instruction string once and record the resulting displacement
(x, y)and headingd. - If the robot returns to the origin, it is trivially bounded, since each repetition retraces the same path.
- If its heading changed (it no longer faces north), the repeated runs trace a closed polygon, so the robot is also bounded.
- 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
LandR: turning left isd - 1(equivalently+3) and turning right isd + 1, both modulo 4. - Testing
d != 0alone: 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.