The Question

Robot Room Cleaner

You are controlling a robot in a room represented as an $m \times n$ binary grid. 0 represents a wall and 1 represents an empty slot. The robot starts at an unknown location, which is guaranteed to be empty. You do not have access to the grid directly, but you can control the robot via an API. The API provides the following methods: - boolean move(): The robot attempts to move one step in its current direction. Returns true if successful, or false if it hits a wall. - void turnLeft() / void turnRight(): The robot turns 90 degrees in place. - void clean(): The robot cleans the current cell. Design an algorithm to clean the entire room. The robot initially faces 'Up'. All boundaries of the grid are walls. Your solution should track visited cells using relative coordinates.

Java

DFS

Backtracking

HashSet

Questions & Insights

Clarifying Questions

What are the maximum dimensions of the grid ($m \times n$)? Knowing this helps determine if a recursive DFS will hit a stack overflow or if a custom Pair class is needed for optimal hashing.

Is the room guaranteed to be a single connected component? If there are isolated empty "islands," the robot cannot reach them from a single starting point.

Is there any penalty for the number of moves or turns? This would dictate whether we need a shortest-path approach (BFS) or if a simple DFS is sufficient.

What should happen if the robot is initialized in a room with no empty cells (other than its start)? The algorithm should clean the start and terminate correctly.

Assumptions

The room is a single connected component of empty cells.

The relative coordinate

(0, 0)

can be assigned to the starting position.

Time complexity is measured by the number of API calls, specifically move(), which should be minimized to

O(N)

where

N

is the number of empty cells.

Standard recursion depth is sufficient for the expected grid size (typically up to

10^4

cells in interview settings).

Thinking Process

Relative Mapping: Since the absolute coordinates and grid dimensions are unknown, treat the starting cell as

(0, 0)

. Maintain a Set of visited coordinates to prevent infinite loops and redundant cleaning.

Backtracking DFS: Use a Depth-First Search to explore the grid. For each cell, attempt to move in all four directions (Up, Right, Down, Left). If a move is successful, recursively call the DFS for the new coordinate.

Physical Backtracking: In a standard DFS on a graph, backtracking is just returning from a function. Here, backtracking requires physical movement. To return to a "parent" cell, the robot must turn 180 degrees, move forward, and turn 180 degrees again to restore its original orientation.

Directional State: Maintain a relative direction (0: Up, 1: Right, 2: Down, 3: Left). When the robot turns right, increment the direction index. This allows the robot to map the move() command to specific coordinate changes

(\Delta x, \Delta y)

Implementation Breakdown

Problem Set

Functional Requirements:

Clean every reachable empty cell exactly once.

Return the robot to a state where it can continue exploring or terminate after all reachable cells are cleaned.

Constraints:

Robot only knows if a move is successful (boolean).

No access to the full map.

Initial orientation is "Up".

Approach

Algorithm: Backtracking DFS (Depth-First Search).

Data Structure: HashSet<String> to track visited coordinates (formatted as "x,y").

Complexity:

Time:

O(N - M)

, where

N

is the total number of cells and

M

is the number of walls. Every empty cell is visited once and each edge (path between cells) is traversed twice (once forward, once backtracking).

Space:

O(N - M)

to store the coordinates of all empty cells in the HashSet and the recursion stack.

Implementation

Wrap Up

Advanced Topics

Memory Optimization: In a very large grid, using a String for the HashSet key can be memory-intensive due to string concatenation and object overhead. Using a custom long hash (e.g., (long)x << 32 | (y & 0xFFFFFFFFL)) or a specialized Coordinate class with a primitive hashCode would be more efficient.

Iterative DFS: An iterative version would require manually managing a stack of (x, y, direction_index) and carefully handling the physical movement of the robot when popping from the stack. This is significantly more complex due to the "physical" nature of the backtracking.

Spiral/Heuristic Exploration: If the room has a specific shape (like a long hallway), certain heuristics might reduce the number of turns, though the asymptotic complexity remains the same.