Robot Clean Room (LC 489)

Problem Statement

You are given a robot in a rectangular room filled with empty and blocked cells. The robot cannot see the room; it can only interact via an API:

move() — moves forward one cell; returns false if blocked (and does not move).
turnLeft() / turnRight() — rotates 90° in place.
clean() — cleans the current cell.

Design an algorithm that cleans the entire room. The starting cell is guaranteed empty.

Constraints:

Room up to 100x200.
Total cells ≤ 5000.
Starting position and orientation are unknown to you.

Difficulty: Hard

Pattern Recognition

Input structure: implicit grid accessed only through a movement API.
What are we doing? exhaustively visiting every reachable cell.
Pattern: DFS with backtracking, using relative coordinates.
Why: you do not know the room size or your absolute position, but you can label cells relative to where you started. DFS recursively tries each direction; after each recursion, restore orientation and position so the parent call can continue.

The "backtrack by physically moving back and un-rotating" is what makes this problem special. It is the canonical Google problem for testing whether you can simulate DFS on a physical system.

Approach

Optimal — DFS With Relative Coordinates and Physical Backtracking

Key Insight: The robot has no GPS. But you, the algorithm, can maintain (x, y) coordinates relative to the start. Keep a visited set of these coordinates. For each unvisited direction, move forward, recurse, then physically restore state.

Directions in order (clockwise): up, right, down, left. Let dirs = [(-1,0), (0,1), (1,0), (0,-1)].

visited = set()

def dfs(x, y, facing):
    visited.add((x, y))
    robot.clean()
    for _ in range(4):
        nx, ny = x + dirs[facing][0], y + dirs[facing][1]
        if (nx, ny) not in visited and robot.move():
            dfs(nx, ny, facing)
            // restore position and orientation
            robot.turnRight(); robot.turnRight()
            robot.move()
            robot.turnRight(); robot.turnRight()
        robot.turnRight()   // try next direction
        facing = (facing + 1) % 4

dfs(0, 0, 0)   // facing arbitrary; problem says starting orientation is 'up' conventionally

Time: O(N - B) cells visited; O(N) moves total where N = total cells. Space: O(N) for visited plus recursion depth.

Key physical actions:

To "turn around" (go back to parent), perform turnRight, turnRight, move, turnRight, turnRight. This faces you back the way you came while preserving the caller's orientation.

Walkthrough

Room (starting at S, facing up):

. . .
. S .
# . .

Tracking in relative coordinates, S = (0,0) facing up.

dfs(0,0, up): clean (0,0).
- Face up, try move: success → (-1, 0). dfs(-1, 0, up).
  - Clean. Try up: blocked or visited? Let's say out of bounds → move fails.
  - turnRight, face right. Try move → (-1, 1). dfs(-1, 1, right).
    - Clean. Keep exploring...
  - After returning, turnRight → face down, etc.
- After all 4 directions, turn around (R,R,move,R,R) back to (0, 0) facing up.
- Face right, try move → (0, 1). Recurse.
- Face down, try move → (1, 0). That's blocked (it's the #) or empty? If ., recurse.
- Face left, try move → (0, -1). Recurse.

Every reachable empty cell gets cleaned exactly once thanks to the visited set.

Implementation

TypeScriptC++

typescript

// Robot interface assumed from LeetCode
interface Robot {
    move(): boolean;
    turnLeft(): void;
    turnRight(): void;
    clean(): void;
}

function cleanRoom(robot: Robot): void {
    const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];  // up, right, down, left
    const visited = new Set<string>();

    const goBack = () => {
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();
    };

    const dfs = (x: number, y: number, facing: number): void => {
        visited.add(`${x},${y}`);
        robot.clean();
        for (let k = 0; k < 4; k++) {
            const d = (facing + k) % 4;
            const nx = x + dirs[d][0];
            const ny = y + dirs[d][1];
            if (!visited.has(`${nx},${ny}`) && robot.move()) {
                dfs(nx, ny, d);
                goBack();
            }
            robot.turnRight();  // rotate robot to next direction for the next iteration
        }
    };

    dfs(0, 0, 0);
}

cpp

class Robot {
public:
    bool move();
    void turnLeft();
    void turnRight();
    void clean();
};

class Solution {
    int dirs[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
    unordered_set<long long> visited;

    long long enc(int x, int y) { return ((long long)x) * 100003LL + y; }

    void goBack(Robot& robot) {
        robot.turnRight(); robot.turnRight();
        robot.move();
        robot.turnRight(); robot.turnRight();
    }

    void dfs(Robot& robot, int x, int y, int facing) {
        visited.insert(enc(x, y));
        robot.clean();
        for (int k = 0; k < 4; k++) {
            int d = (facing + k) % 4;
            int nx = x + dirs[d][0];
            int ny = y + dirs[d][1];
            if (!visited.count(enc(nx, ny)) && robot.move()) {
                dfs(robot, nx, ny, d);
                goBack(robot);
            }
            robot.turnRight();
        }
    }

public:
    void cleanRoom(Robot& robot) {
        dfs(robot, 0, 0, 0);
    }
};

Watch out:
Your facing variable (logical) must stay in sync with the robot's physical orientation. Every turnRight() in the loop must update facing effectively — easiest to compute the next direction as (facing + k) % 4 for each of the 4 attempts.
Forgetting goBack after recursion strands the robot one cell away from where the caller expects. The parent's next turnRight then moves wrong.
Using a 2D visited array requires knowing room bounds up front. Use a hash set keyed by (x, y) instead.

Complexity Analysis

	Time	Space
DFS	O(4 * (N - B)) moves	O(N - B) visited + O(N - B) recursion

Where N is total cells and B is blocked cells. Each empty cell is visited exactly once; from each, you attempt at most 4 neighbors.

Bottleneck: the robot physically moves once per edge in the exploration DFS tree, which is Θ(N).

Edge Cases

1x1 room — clean the cell and return. DFS terminates after four turnRight calls.
Fully open room — DFS visits every cell; stack depth up to N.
Isolated cells — impossible per problem: starting cell is empty and room is connected.
Dead-end corridors — backtracking via goBack pops back out.
Large room (5000 cells) — recursion can stack 5000 deep. Mention converting to iterative DFS with an explicit stack if interviewer pushes on it.

LC 200 — Number of Islands — Grid DFS with explicit coordinates; the analog without physical constraints.
LC 490 — The Maze — Ball rolls until it hits a wall; similar grid DFS but different movement rules.
LC 317 — Shortest Distance from All Buildings — Grid BFS with physical-like constraints.
LC 778 — Swim in Rising Water — Dijkstra on a grid; contrasts with the DFS-based approach.

What Is Expected at Each Level

Junior: Struggle with the physical backtracking. Write pseudocode, get the DFS skeleton, and work through the goBack with hints.

Mid-level: Correctly implement the DFS with relative coordinates and goBack, handle the visited-set keying, and explain why the direction rotation must stay in sync.

Senior (L4 target): Write the whole thing cleanly, discuss stack-size worries for large rooms, optionally sketch the iterative equivalent, and show awareness of similar "agent on an unknown graph" patterns like exploration algorithms and robot localization.

Robot Clean Room (LC 489) ​

Problem Statement ​

Pattern Recognition ​

Approach ​

Optimal — DFS With Relative Coordinates and Physical Backtracking ​

Walkthrough ​

Implementation ​

Complexity Analysis ​

Edge Cases ​

Related Problems ​

What Is Expected at Each Level ​