LeetCode 489: Robot Room Cleaner Solution in Python – A Step-by-Step Guide

What Is LeetCode 489: Robot Room Cleaner?

In LeetCode 489: Robot Room Cleaner, you’re given a robot interface (Robot) with methods to move forward (move()), turn left or right (turnLeft(), turnRight()), and clean the current cell (clean()), but no map of the room. The room is a grid with obstacles (1) and open spaces (0), and the robot starts at an unknown open cell facing north. Your task is to implement a function to clean every accessible cell using only these methods, returning nothing (the robot cleans in-place). For example, in a room like [[1,1,1],[1,0,1],[1,1,1]], starting at [1,1], the robot must clean [1,1] and backtrack to cover all reachable spots. It’s like guiding a blind robot through a maze, relying on trial and error to sweep it clean.

Problem Statement

• Input: robot (Robot)—interface with methods:
• move(): bool—moves forward if possible, returns True if moved.
• turnLeft(): None—turns 90° left.
• turnRight(): None—turns 90° right.
• clean(): None—cleans current cell.
• Output: None—clean all accessible cells in-place.
• Rules:
• Start at unknown open cell, facing north.
• Clean every reachable cell exactly once.
• Use only robot’s methods, no map access.

Constraints

• Room is an m x n grid, \( 1 \leq m, n \leq 50 \).
• Contains 0 (open) and 1 (obstacle).
• Robot starts at an open cell (0).
• At least one open cell exists.

Examples to Get Us Started

• Input: Room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,0,1,1,0,1,1],[0,1,1,0,0,0,0,0],[1,1,1,0,1,1,1,1]], Start = [1,1], Facing north.
• Output: None (Robot cleans all accessible 0s).
• Input: Room = [[1,1,1],[1,0,1],[1,1,1]], Start = [1,1].
• Output: None (Robot cleans [1,1]).

Understanding the Problem: Navigating the Maze

To solve LeetCode 489: Robot Room Cleaner in Python, we need to program the robot to clean every accessible cell in an unseen grid, using only its movement and cleaning methods. A naive approach—randomly moving and cleaning—could miss cells or loop indefinitely, inefficient for a 50x50 grid. The key? Use DFS with backtracking and direction tracking to systematically explore and clean all reachable cells, maintaining a visited set to avoid cycles. We’ll explore:

• Best Solution (DFS with Backtracking and Direction Tracking): O(m * n) time, O(m * n) space—fast and optimal (m, n = grid dimensions).
• Alternative Solution (Brute Force Simulation): O((m * n)^2) time, O(m * n) space—simple but slow.

Let’s dive into the DFS solution—it’s the janitor’s smart broom we need.

Best Solution: DFS with Backtracking and Direction Tracking

Why This Is the Best Solution

The DFS with backtracking and direction tracking is the top pick because it’s O(m * n) time (m * n = grid size) and O(m * n) space, efficiently cleaning all accessible cells by systematically exploring each direction (north, east, south, west) from the starting point, backtracking to previous cells when blocked, and using a visited set to avoid revisiting. It leverages the robot’s local control to mimic a global search, ensuring completeness. It’s like guiding the robot with a mental map, sweeping every nook without getting lost—clever and precise!

How It Works

Here’s the strategy:

• Step 1: Track position and direction:
• Use (x, y) coordinates, direction (0=north, 1=east, 2=south, 3=west).
• Visited set to mark cleaned cells.
• Step 2: DFS function:
• Clean current cell, mark visited.
• For each of 4 directions:
• Turn to face direction.
• If can move, go forward, recurse, backtrack.
• Turn back to original direction.
• Step 3: Backtrack by reversing move:
• Turn 180°, move back, turn 180° again.
• Step 4: Start DFS from (0,0), facing north.
• Why It Works:
• DFS ensures all reachable cells explored.
• Backtracking returns robot to start, avoiding loops.

Step-by-Step Example

Example: Room = [[1,1,1],[1,0,1],[1,1,1]], Start = [1,1], North

• Init: (x, y) = (0, 0) relative, dir = 0, visited = {(0, 0)}.
• Clean [1,1]: Add (0, 0).
• Dir 0 (North): Blocked ([0,1] = 1), stay.
• Dir 1 (East): Blocked ([1,1] = 1), stay.
• Dir 2 (South): Blocked ([2,1] = 1), stay.
• Dir 3 (West): Blocked ([1,0] = 1), stay.
• End: All reachable (just [1,1]) cleaned.
• Result: Robot cleaned [1,1].

Example: Room = [[0,0],[0,0]], Start = [0,0]

• (0,0), North: Clean, visited = {(0,0)}.
• North: Move to (-1,0), clean, backtrack.
• East: Move to (0,1), clean, backtrack.
• South: Move to (1,0), clean, backtrack.
• Result: All 4 cells cleaned.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def cleanRoom(self, robot):
        # Directions: north, east, south, west
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        visited = set()

        def dfs(x: int, y: int, dir: int):
            # Step 1: Clean current cell
            robot.clean()
            visited.add((x, y))

            # Step 2: Explore all 4 directions
            for d in range(4):
                new_dir = (dir + d) % 4
                new_x = x + directions[new_dir][0]
                new_y = y + directions[new_dir][1]

                # Turn to face new direction
                while dir != new_dir:
                    robot.turnRight()
                    dir = (dir + 1) % 4

                # If not visited and can move
                if (new_x, new_y) not in visited and robot.move():
                    dfs(new_x, new_y, new_dir)
                    # Step 3: Backtrack
                    robot.turnRight()
                    robot.turnRight()
                    robot.move()
                    robot.turnRight()
                    robot.turnRight()

        # Step 4: Start DFS from (0,0), facing north
        dfs(0, 0, 0)

• Line 4-5: Define directions (north, east, south, west), init visited set.
• Line 7-26: DFS:
• Clean current cell, mark visited.
• For each direction:
• Adjust robot’s facing (turnRight until match).
• If unvisited and movable, recurse.
• Backtrack: turn 180°, move back, turn 180°.
• Line 29: Start DFS at (0,0), north (dir=0).
• Time Complexity: O(m * n)—visits each cell once.
• Space Complexity: O(m * n)—visited set.

It’s like a robotic maze sweeper!

Alternative Solution: Brute Force Simulation

Why an Alternative Approach?

The brute force simulation—O((m * n)^2) time, O(m * n) space—moves the robot exhaustively in a predefined pattern (e.g., spiral or zigzag), cleaning and tracking visited cells without backtracking optimization, retrying moves until all are covered. It’s slow but intuitive, like sweeping randomly until every spot shines. Good for small grids or learning!

How It Works

• Step 1: Track visited cells, move in pattern (e.g., north then east).
• Step 2: If blocked, turn and retry.
• Step 3: Continue until all visited or stuck.
• Step 4: No explicit return (in-place cleaning).

Step-by-Step Example

Example: Room = [[0,0],[0,0]]

• Start (0,0): Clean, north → (-1,0), clean.
• East: (0,1), clean, south → (1,1), clean.
• Result: All cleaned, inefficient path.

Code for Brute Force (Simplified)

Copy codeclass Solution:
    def cleanRoom(self, robot):
        visited = set()
        x, y = 0, 0
        dir = 0  # North
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

        while True:
            robot.clean()
            visited.add((x, y))
            moved = False
            for _ in range(4):
                new_x = x + directions[dir][0]
                new_y = y + directions[dir][1]
                if (new_x, new_y) not in visited and robot.move():
                    x, y = new_x, new_y
                    moved = True
                    break
                robot.turnRight()
                dir = (dir + 1) % 4
            if not moved:
                break  # Stuck, assume all cleaned (simplified)

• Line 4-15: Move in direction, clean, turn if blocked.
• Time Complexity: O((m * n)^2)—revisits possible.
• Space Complexity: O(m * n)—visited set.

It’s a slow robo-sweeper!

Comparing the Two Solutions

• DFS with Backtracking (Best):
• Pros: O(m * n), efficient, complete.
• Cons: O(m * n) space.
• Brute Force (Alternative):
• Pros: O((m * n)^2), simple concept.
• Cons: Slow, may miss cells.

DFS wins for efficiency.

Edge Cases and Examples

• Single cell: Cleans [0].
• All obstacles: Cleans start only.
• Complex maze: DFS covers all.

DFS handles all perfectly.

Complexity Recap

• DFS: Time O(m * n), Space O(m * n).
• Brute Force: Time O((m * n)^2), Space O(m * n).

DFS is the champ.

Key Takeaways

• DFS: Backtrack smartly.
• Brute Force: Sweep blindly.
• Python Tip: DFS navigates—see [Python Basics](/python/basics).

Final Thoughts: Sweep That Room

LeetCode 489: Robot Room Cleaner in Python is a robotic maze adventure. DFS with backtracking is your fast broom, while brute force is a slow mop. Want more maze challenges? Try LeetCode 200: Number of Islands or LeetCode 490: The Maze. Ready to clean some rooms? Head to Solve LeetCode 489 on LeetCode and sweep it today—your coding skills are robo-ready!