LeetCode 489 - Robot Room Cleaner

LeetCode Problem 489

Difficulty: 🔴 Hard
Topics: Backtracking, Interactive

Solution

Problem Understanding

This problem is an interactive backtracking problem where we must control a robot without directly seeing the room layout. Unlike traditional grid traversal problems, we are not given access to the actual room matrix during execution. The only way to explore the environment is through the robot's API.

The room is conceptually a binary grid:

• 1 represents an empty cell the robot can enter.
• 0 represents a wall or blocked cell.

The robot begins at some unknown valid empty cell, facing upward. We do not know:

• The robot's absolute coordinates
• The dimensions of the room
• Where the walls are located

Instead, we can only interact through four API calls:

• move() attempts to move forward
• turnLeft() rotates the robot 90 degrees counterclockwise
• turnRight() rotates the robot 90 degrees clockwise
• clean() cleans the current cell

The goal is to ensure every reachable empty cell gets cleaned exactly once or at least once.

The important challenge is that this is effectively a blindfolded graph traversal problem. Since we do not know the map beforehand, we must build our own virtual coordinate system while exploring.

The constraints tell us that:

• The room can contain up to 100 * 200 = 20,000 cells.
• Every empty cell is reachable from the starting position.
• The robot starts on a valid empty cell.
• The borders are guaranteed to be walls, so the robot cannot leave the room.

These guarantees are important because they allow us to perform a complete traversal without worrying about disconnected reachable components or infinite movement outside bounds.

Several edge cases are especially important:

• A room containing only one cell
• Narrow corridors where many moves fail
• Cyclic paths where the robot can revisit cells through different routes
• Large open areas where naive revisiting would cause exponential work
• Maintaining the robot's orientation correctly after recursive exploration

The hardest part of the problem is not traversal itself, but ensuring the robot always returns to its previous position and orientation after exploring a direction.

Approaches

Brute Force Approach

A naive strategy would be to repeatedly move in all possible directions without remembering where the robot has already been. The robot could recursively attempt every possible movement sequence.

This approach eventually cleans all reachable cells because every path is explored. However, it performs enormous redundant work because the robot revisits the same cells repeatedly through different paths.

For example, in an open room, the robot could endlessly cycle between neighboring cells. Without tracking visited states, the traversal becomes effectively exponential.

Another problem is orientation management. If we do not carefully restore the robot's direction after recursion, future exploration becomes inconsistent and difficult to reason about.

Because of repeated revisits, this brute-force method is impractical for large rooms.

Optimal Approach

The key observation is that the room forms an implicit graph:

• Each empty cell is a node
• Adjacent reachable cells form edges

We can therefore use Depth-First Search (DFS) with backtracking.

Since the robot does not know real coordinates, we create a virtual coordinate system:

• The starting position is (0, 0)
• Moving up decreases the row
• Moving right increases the column
• Moving down increases the row
• Moving left decreases the column

We maintain a visited set so each cell is explored only once.

The critical technique is backtracking:

1. Move into a neighboring cell
2. Recursively clean that area
3. Return the robot to the original cell
4. Restore the original orientation

This guarantees that after exploring one direction, the robot is in the exact same state as before, allowing exploration of remaining directions safely.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Repeatedly revisits cells and explores redundant paths
Optimal DFS + Backtracking	O(N)	O(N)	Visits each reachable cell once, where N is the number of empty cells

Algorithm Walkthrough

Step 1: Define Direction Vectors

We represent the four directions as:

• Up: (-1, 0)
• Right: (0, 1)
• Down: (1, 0)
• Left: (0, -1)

We also assign direction indices:

• 0 = up
• 1 = right
• 2 = down
• 3 = left

This allows us to compute new coordinates consistently.

Step 2: Maintain a Visited Set

Because the robot can revisit cells through different paths, we store visited coordinates in a hash set.

When we enter a cell:

• Add its coordinates to visited
• Clean the current cell

This prevents infinite loops and redundant exploration.

Step 3: Explore All Four Directions

For each cell, we attempt exploration in all four directions relative to the robot's current orientation.

For each direction:

1. Compute the neighbor coordinates
2. If not visited:

• Attempt move()

• If successful:

• Recursively explore

• Backtrack afterward

3. Rotate right to align for the next direction

Even if movement fails because of a wall, we still rotate and continue checking other directions.

Step 4: Backtrack Correctly

After recursive exploration, the robot is deeper in the DFS tree.

We must restore the previous state exactly.

To return to the prior cell:

1. Turn around 180 degrees
2. Move forward
3. Turn around again

This returns:

• Position to the parent cell
• Orientation to its original direction

This step is the core invariant of the algorithm.

Step 5: Continue Until DFS Completes

Eventually all reachable cells are visited.

Because every reachable cell is explored once and every recursive call restores state properly, the entire room is cleaned successfully.

Why it works

The algorithm maintains the invariant that after every recursive DFS call finishes, the robot returns to the same position and orientation it had before the call began.

Because each reachable cell is added to the visited set exactly once, the DFS traversal eventually explores every accessible cell without infinite loops. Backtracking guarantees consistent exploration order and prevents the robot from getting lost relative to the virtual coordinate system.

Python Solution

# """
# This is the robot's control interface.
# You should not implement it, or speculate about its implementation
# """
# class Robot:
#     def move(self):
#         pass
#
#     def turnLeft(self):
#         pass
#
#     def turnRight(self):
#         pass
#
#     def clean(self):
#         pass

from typing import Set, Tuple

class Solution:
    def cleanRoom(self, robot) -> None:
        directions = [
            (-1, 0),  # up
            (0, 1),   # right
            (1, 0),   # down
            (0, -1)   # left
        ]

        visited: Set[Tuple[int, int]] = set()

        def go_back() -> None:
            robot.turnRight()
            robot.turnRight()

            robot.move()

            robot.turnRight()
            robot.turnRight()

        def dfs(row: int, col: int, direction: int) -> None:
            visited.add((row, col))
            robot.clean()

            for i in range(4):
                new_direction = (direction + i) % 4

                dr, dc = directions[new_direction]
                new_row = row + dr
                new_col = col + dc

                if (new_row, new_col) not in visited:
                    if robot.move():
                        dfs(new_row, new_col, new_direction)
                        go_back()

                robot.turnRight()

        dfs(0, 0, 0)

The implementation begins by defining the four movement directions in clockwise order. This ordering is important because the robot rotates right after each exploration attempt.

The visited set stores virtual coordinates. Since the real room coordinates are unknown, the algorithm treats the starting position as (0, 0) and derives all other positions relative to it.

The go_back() helper performs the backtracking operation. The robot turns around, moves one step backward, and restores its orientation. This guarantees that DFS recursion behaves correctly.

The dfs() function is responsible for exploring and cleaning reachable cells.

When entering a cell:

1. Mark it visited
2. Clean it

Then the function checks all four directions. For each direction:

• Compute the neighbor coordinates
• Skip already visited cells
• Attempt movement
• Recurse if movement succeeds
• Backtrack afterward

Finally, the robot rotates right to prepare for checking the next direction.

The recursive structure mirrors a standard DFS traversal while carefully maintaining robot orientation.

Go Solution

/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * type Robot struct {
 * }
 *
 * // Returns true if the cell in front is open and robot moves into the cell.
 * // Returns false if the cell in front is blocked and robot stays in the current cell.
 * func (robot *Robot) Move() bool {}
 *
 * // Robot will stay on the same cell after calling TurnLeft/TurnRight.
 * // Each turn will be 90 degrees.
 * func (robot *Robot) TurnLeft() {}
 * func (robot *Robot) TurnRight() {}
 *
 * // Clean the current cell.
 * func (robot *Robot) Clean() {}
 */

func cleanRoom(robot *Robot) {
	directions := [][]int{
		{-1, 0}, // up
		{0, 1},  // right
		{1, 0},  // down
		{0, -1}, // left
	}

	type Position struct {
		row int
		col int
	}

	visited := make(map[Position]bool)

	var goBack func()
	goBack = func() {
		robot.TurnRight()
		robot.TurnRight()

		robot.Move()

		robot.TurnRight()
		robot.TurnRight()
	}

	var dfs func(row, col, direction int)

	dfs = func(row, col, direction int) {
		visited[Position{row, col}] = true
		robot.Clean()

		for i := 0; i < 4; i++ {
			newDirection := (direction + i) % 4

			dr := directions[newDirection][0]
			dc := directions[newDirection][1]

			newRow := row + dr
			newCol := col + dc

			if !visited[Position{newRow, newCol}] {
				if robot.Move() {
					dfs(newRow, newCol, newDirection)
					goBack()
				}
			}

			robot.TurnRight()
		}
	}

	dfs(0, 0, 0)
}

The Go implementation closely follows the Python version.

The primary difference is that Go does not have tuple hashing built in, so we define a Position struct and use it as the map key.

The DFS logic and backtracking behavior are identical.

Go recursion depth is acceptable for the given constraints because the maximum number of reachable cells is at most 20,000, which is typically manageable in LeetCode's environment for this problem.

No integer overflow concerns exist because coordinates remain within reasonable bounds.

Worked Examples

Example 1

Input:

room =
[
  [1,1,1,1,1,0,1,1],
  [1,1,1,1,1,0,1,1],
  [1,0,1,1,1,1,1,1],
  [0,0,0,1,0,0,0,0],
  [1,1,1,1,1,1,1,1]
]

Robot starts at (1, 3) facing up.

Since the algorithm does not know real coordinates, it treats this as virtual coordinate (0, 0).

Initial State

Variable	Value
Position	(0, 0)
Direction	Up (0)
Visited	{}

Step 1

Robot cleans current cell.

Action	Result
clean()	Current cell cleaned
visited	{(0,0)}

Step 2

Attempt moving upward.

Suppose movement succeeds.

Variable	Value
New Position	(-1, 0)
Direction	Up

Recursive DFS begins.

Step 3

Robot continues recursively exploring reachable neighbors.

Whenever recursion finishes:

Action	Purpose
Turn 180 degrees	Face parent
Move()	Return to parent
Turn 180 degrees	Restore orientation

This process repeats until every reachable cell has been visited.

Eventually all open cells are cleaned.

Example 2

Input:

room = [[1]]

Initial State

Variable	Value
Position	(0,0)
Direction	Up
Visited	{}

Execution

Step	Action
1	Add (0,0) to visited
2	Clean current cell
3	All four move attempts fail
4	DFS terminates

The single cell is successfully cleaned.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Each reachable cell is visited once
Space	O(N)	Visited set and recursion stack store reachable cells

Here, N represents the number of reachable empty cells.

Although the robot may rotate many times, each cell causes only constant additional work. Every edge between neighboring cells is traversed at most a constant number of times because DFS explores and backtracks exactly once per successful movement.

The recursion stack can grow up to O(N) in the worst case, such as a long corridor.

Test Cases

# These are conceptual tests because the real problem is interactive.

# Example 1
room = [
    [1,1,1,1,1,0,1,1],
    [1,1,1,1,1,0,1,1],
    [1,0,1,1,1,1,1,1],
    [0,0,0,1,0,0,0,0],
    [1,1,1,1,1,1,1,1]
]
row = 1
col = 3
assert room[row][col] == 1  # Valid starting position

# Example 2
room = [[1]]
row = 0
col = 0
assert room[row][col] == 1  # Single-cell room

# Narrow corridor
room = [[1,1,1,1,1]]
assert all(cell == 1 for cell in room[0])  # Linear traversal

# Fully blocked except start
room = [
    [0,0,0],
    [0,1,0],
    [0,0,0]
]
assert room[1][1] == 1  # Only one reachable cell

# Large open room
room = [
    [1,1,1],
    [1,1,1],
    [1,1,1]
]
assert sum(sum(row) for row in room) == 9  # All cells reachable

# Cyclic paths
room = [
    [1,1,1],
    [1,0,1],
    [1,1,1]
]
assert room[1][1] == 0  # Central obstacle creates cycle

# Complex maze
room = [
    [1,0,1,1],
    [1,1,1,0],
    [0,1,0,1],
    [1,1,1,1]
]
assert room[0][0] == 1  # Reachable maze traversal

Test Summary

Test	Why
Single cell room	Verifies minimal input
Narrow corridor	Tests deep recursion path
Fully blocked except start	Ensures failed movement handling
Large open room	Tests extensive exploration
Cyclic layout	Verifies visited set prevents loops
Complex maze	Tests mixed walls and traversal paths

Edge Cases

Single Reachable Cell

A room may contain only one accessible cell. In this case, all movement attempts fail immediately. A buggy implementation might recurse unnecessarily or mishandle orientation changes after failed moves.

This implementation handles it naturally because the DFS cleans the current cell, attempts four failed moves, rotates appropriately, and terminates.

Cyclic Paths

Open rooms often contain cycles where the robot can return to previously visited cells through different paths. Without a visited set, the robot would loop infinitely.

The implementation avoids this by storing every visited coordinate in a hash set before exploring neighbors.

Long Corridors

A narrow hallway can produce very deep recursion. Incorrect backtracking would leave the robot facing the wrong direction when returning from recursion.

The go_back() helper guarantees that after recursive exploration, both the robot's position and orientation are restored exactly, making subsequent exploration correct.

Walls Adjacent to Every Direction

A cell may be surrounded by walls on multiple sides. An incorrect solution might assume movement succeeded or fail to rotate properly after blocked movement.

This implementation always rotates after each direction attempt, regardless of whether movement succeeds, ensuring consistent orientation management.