Skip to main content

489 - Robot Room Cleaner

Difficulty: Hard | Pattern: DFS + Backtracking (Spiral) | Company tags: Google, Amazon

Problem Statement​

You are controlling a robot that cleans a room. The robot has the following API:

  • robot.move() — moves forward, returns false if blocked
  • robot.turnRight() — turns right 90°
  • robot.turnLeft() — turns left 90°
  • robot.clean() — cleans current cell

You don't know the room's layout. Return after cleaning all reachable cells.

Approach: DFS with Backtracking — O(4^(m×n))​

Key insight: Use DFS from the starting cell, tracking visited cells by relative coordinates. After exploring all 4 directions, backtrack by turning 180°, moving one step back, and turning 180° again.

def cleanRoom(robot):
    visited = set()
    directions = [(-1,0),(0,1),(1,0),(0,-1)]  # up, right, down, left
    
    def go_back():
        robot.turnRight()
        robot.turnRight()
        robot.move()
        robot.turnRight()
        robot.turnRight()
    
    def dfs(r, c, d):
        robot.clean()
        visited.add((r, c))
        
        for i in range(4):
            new_d = (d + i) % 4
            dr, dc = directions[new_d]
            nr, nc = r + dr, c + dc
            
            if (nr, nc) not in visited and robot.move():
                dfs(nr, nc, new_d)
                go_back()
            
            robot.turnRight()
    
    dfs(0, 0, 0)

Algorithm Flow​

Key Insight: Direction Encoding​

We start facing "up" (direction 0). Each turnRight() increments direction by 1 mod 4. The directions array maps direction index to (dr, dc).

Backtracking Logic​

After exploring from a cell, we must return to the calling cell in the same orientation:

  1. Turn 180° (two right turns)
  2. Move forward (back to parent)
  3. Turn 180° again (restore orientation)

Dry Run​

Starting at (0,0) facing up:

  1. Clean (0,0), try up: if movable → go to (-1,0), recurse, come back
  2. Turn right, try right, etc.
  3. Explores entire reachable region, backing up at walls/visited

Complexity​

  • Time: O(4^(m×n)) worst case, but O(n) where n = accessible cells
  • Space: O(n) for visited set and recursion

Key Terms​

TermDefinition
BacktrackingUndoing a move after exploring a branch so the search state returns to how it was before the branch was taken.
Relative coordinatesGrid positions tracked from the robot's unknown starting point (0,0) since the true room layout is never known.
Visited setHash set of explored (r, c) cells used to avoid re-cleaning or re-entering the same cell.
Direction encodingRepresenting heading as an integer 0-3 so turnRight() maps cleanly to (d + 1) % 4.

FAQ​

  1. Why track relative coordinates instead of the room's actual grid? The robot has no map or absolute coordinates — only relative movement — so DFS must build its own coordinate system starting at the origin.
  2. Why is backtracking implemented as two 180° turns plus a move instead of just "moving back"? The robot API only exposes move(), turnLeft(), turnRight(), and clean() — there's no reverse-move primitive, so returning to the parent cell requires physically turning around, moving forward, and turning back to the original heading.
  3. Can this be solved without recursion? Yes, with an explicit stack storing (r, c, direction) triples, but the code is less readable than the natural DFS recursion.
  4. What happens if the room has disconnected regions? The robot can only clean cells reachable from the start; disconnected pockets are never visited since there's no teleportation.
  5. Why is the worst-case time O(4^(m×n)) instead of O(m×n)? The bound accounts for the exploration and backtracking overhead per cell in the worst arrangement of obstacles, though in practice each of the n reachable cells is visited a bounded number of times, giving effectively O(n) work.

Quick Revision​

  • Problem: clean every reachable cell of an unknown room using only relative move/turn commands.
  • Core idea: DFS from the start, using relative (r, c) coordinates since no map exists.
  • Track visited cells in a set keyed by relative coordinates.
  • At each cell: clean it, then try all 4 directions in order, turning right after each attempt.
  • Only descend into a neighbor if it's unvisited and move() succeeds.
  • Backtrack after each recursive call: turn 180°, move, turn 180° again to restore heading and position.
  • Encode heading as 0-3 mapped to (dr, dc) pairs so turns are simple modular arithmetic.
  • Time is bounded by the number of reachable cells; space is the visited set plus recursion depth.