Robot Room Cleaner - Solution & Explanation

Problem Overview: You control a robot placed in an unknown room represented as a grid. The robot can move forward, turn left/right, and clean the current cell. Walls block movement and the layout is not given in advance. The goal is to clean every reachable cell exactly once using only the robot's movement API.

Approach 1: DFS Exploration with Backtracking (O(n) time, O(n) space)

The standard solution models the room as an implicit graph and performs a depth‑first search using backtracking. Since the grid is unknown, you track visited cells using coordinates relative to the starting position, typically with a set. The robot explores four directions from each cell, recursively moving when move() succeeds. After exploring a branch, you must physically move the robot back to the previous cell using a sequence of turns and a reverse move, ensuring the robot’s orientation is restored before continuing exploration.

This technique systematically explores every reachable cell exactly once. Direction management is critical: maintain an array of four directions and rotate the robot after each attempt so the exploration order remains consistent. The total work is proportional to the number of accessible cells because each cell is visited once and each edge (movement attempt) is processed a constant number of times.

Approach 2: Graph Traversal with Coordinate Mapping (O(n) time, O(n) space)

Another way to think about the solution is explicit graph traversal while building a coordinate map of the discovered environment. Each successful movement reveals a new node in the graph, and failed movements reveal walls. Using DFS or BFS, you store discovered coordinates and continue exploring neighbors that have not been visited. In practice, DFS combined with backtracking works best because the robot must physically return to previous cells to explore other branches.

The key challenge is synchronizing logical coordinates with the robot’s real orientation. After exploring a direction, the algorithm performs a backtrack step: turn 180 degrees, move back, then restore the original orientation. Without this step the robot’s position would drift away from the recursion state.

Recommended for interviews: Interviewers expect the DFS backtracking approach. A brute-force idea of exploring blindly without visited tracking leads to infinite loops and shows weak understanding. The correct solution demonstrates control over state restoration, direction handling, and graph exploration in an unknown environment. Clean implementations usually maintain a visited set of coordinates, iterate through four directions, rotate the robot each iteration, and perform a precise backtrack sequence after recursion.