Problem statement
Write void cleanRoom(Robot robot) to clean every open cell reachable from the robot’s starting position, using only its control API. The robot starts on an open cell facing up. Walls and room boundaries remain fixed.
| API | Meaning |
|---|---|
boolean move() |
Move one cell forward if possible. Return true after moving; otherwise return false without changing the cell or heading. |
void turnLeft() |
Rotate 90° counterclockwise without moving. |
void turnRight() |
Rotate 90° clockwise without moving. |
void clean() |
Clean the cell currently occupied. It does not clean neighboring cells. |
The room matrices in the examples initialize a hidden test robot. Your solution does not receive that matrix, its dimensions, or the starting row and column. The output is a cleaned room, not an integer returned by the method.
This is LeetCode 489, Robot Room Cleaner, listed as Hard/Premium in its public metadata. The locked statement’s numeric bounds are not reproduced here. Our examples below are small teaching cases.
We will clean each reachable cell once. Reentering a cleaned cell while returning through a passage is allowed; it does not mean we should clean or explore that cell again.
Constraints & requirements
- CONTRACT
- The robot starts on an open cell facing up; walls and room boundaries remain fixed. move advances one cell in its current heading on success and leaves it in place on failure; turns rotate 90 degrees without moving. Example grids initialize a hidden test robot only. Public LeetCode metadata lists 489, Hard, Premium; no hidden numeric bounds are claimed.
Examples 3 test cases
Example 1 Case 1
- Input
room=[[1,1],[1,0]]; start=(0,0); facing=up- Output
Clean (0,0), (0,1) and (1,0) once each; return void
The right and down branches are reachable. The bottom-right wall is not cleaned. This implementation also ends at its original cell facing up.
Example 2 Case 2
- Input
room=[[1]]; start=(0,0); facing=up- Output
Clean the only cell once; return void
Every attempted movement hits the boundary. Four loop turns restore the initial heading without leaving the cell.
Example 3 Case 3
- Input
room=[[1,1],[1,1]]; start=(1,1); facing=up- Output
Clean all four cells once; return void
The room contains a cycle. Permanent discovered-coordinate marks prevent repeat exploration; relative coordinates may be negative.
Hints Optional
01Hint 1
Call the unknown starting cell (0,0). Successful moves give neighboring relative coordinates without revealing the hidden room matrix.
02Hint 2
A recursive call must finish in the same physical cell and heading it entered. Java returning from a function does not move a robot.
03Hint 3
Try four clockwise headings. After a successful child returns, turn twice, move back, turn twice again, then make the loop’s one right turn. Keep discovered marks permanently.
You can ask a robot to move, turn or clean. You cannot look at its room map, ask for its coordinates, or send it directly to a chosen square.
The interesting part is not just finding a DFS order. It is making sure that the robot is physically where your Java code thinks it is—especially after a recursive call returns.
How to think before coding
Separate two questions:
- What should the search explore next? Remember discovered cells and try four neighboring positions.
- Where is the robot now? Maintain its physical position and facing direction while carrying out those choices.
Ordinary grid DFS can read room[r][c]. Here, trying robot.move() is how you discover whether the cell ahead is open. A successful move creates a child search; a failed move creates no child.
Returning from a method only restores Java’s execution point. It does not drive a robot back to the caller’s cell. That missing physical action is the central backtracking step.
Brute force and the improvement
A finite but wasteful baseline explores every simple route from the start:
- Keep a set of coordinates on the current route so a route cannot cycle forever.
- Try every unreserved neighboring cell through the robot API.
- Return physically after each child, then remove that child’s route reservation.
- Keep a separate set of already-cleaned cells if cleaning should happen only once, but still explore those cells again through other routes.
This is correct, but different routes repeatedly explore the same area. If A cells are reachable, a simple route has at most A−1 moves. A loose upper bound is O(4^A) exploration work and O(A) working space, assuming constant-time coordinate-set operations. This is not the cost of the improved solution.
What information changes the answer? Once a cell has been fully explored, reaching it through another route cannot reveal a new neighbor. We do not need all routes; we need all cells.
Use a permanent discovered set instead of removing a cell when its call finishes. This turns route enumeration into graph traversal: enter and expand each reachable cell once. A random walk or a recursion with no cycle guard is not a valid terminating brute-force solution.
Intuition: create a map from movements
Give the start a relative coordinate
Call the starting cell (0,0). This is a coordinate we choose, not a claim about its real position in the hidden matrix.
| Heading | Direction number | Relative change |
|---|---|---|
| Up | 0 | row − 1 |
| Right | 1 | column + 1 |
| Down | 2 | row + 1 |
| Left | 3 | column − 1 |
If the robot successfully moves up, the new relative coordinate is (-1,0). Negative values are ordinary coordinates here, not out-of-bounds errors. The physical API—not a comparison with matrix dimensions—decides whether a move is possible.
The same physical cell always receives the same relative coordinate: every successful movement changes it by the corresponding direction vector. Different paths therefore agree about previously discovered cells.
Synchronize the direction number with actual turns
The clockwise order is up → right → down → left → up. It agrees with turnRight() and with adding one modulo four.
A call begins at (row,col) facing direction. Before loop attempt i, the robot must face:
nextDirection = (direction + i) % 4.
The direction calculation does not itself turn the robot. The unconditional robot.turnRight() at the end of each attempt supplies that physical turn. It is needed after a wall, after a visited-cell skip, and after a successful branch.
Make each call restore its entry pose
The useful promise is:
InsightA call starts in its own cell facing its entry direction, explores its reachable undiscovered branches, then finishes in that same cell facing that same direction.
“Pose” means position plus heading. Restoring only one of them is not enough.
The child finishes in its child cell, not in the parent’s cell. Its waiting parent calls goBack to cross the edge in reverse. Only then can the parent’s next loop iteration use its original row and column safely.
Algorithm
- Create a fresh discovered set and begin at relative
(0,0), direction 0. - Mark the current coordinate and clean the current physical cell.
- For each of four clockwise headings, calculate the prospective relative neighbor.
- Check the discovered set before calling
move(). A known neighbor needs no new physical exploration. - If the neighbor is new and
move()succeeds, recurse from that neighbor and heading. - After the child returns, physically return using
goBack. - Turn right once, whether the attempt succeeded or not.
- After four attempts, return. Four loop turns have restored the entry heading.
There is no “row equals number of rows” base case, because your method does not know the dimensions. A blocked or discovered neighbor creates no child; a frame finishes when all four attempts are done. The finite room and permanent discovery marks bound the number of entered frames.
Java solution
The method uses only the Robot API. RoomCell is an immutable Java record with value-based equality, so a HashSet can recognize the same coordinate without guessing a room width.
The judge supplies Robot. The interface below is included only to let the complete example compile locally; omit that interface in a judge that already defines it. The one-cell test robot in main is a local smoke test, not a way to access a real robot’s hidden map.
import java.util.*;
// For local compilation only. Omit this interface when the judge supplies Robot.
interface Robot {
boolean move(); // Move one cell forward; false means stay in place.
void turnLeft(); // Rotate 90 degrees without changing cells.
void turnRight(); // Rotate 90 degrees without changing cells.
void clean(); // Clean only the cell currently occupied.
}
class Solution {
// Clockwise order must agree with the turnRight at the end of every attempt.
private static final int[][] ROOM_DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private record RoomCell(int row, int col) {} // Immutable, value-based coordinate key.
public void cleanRoom(Robot robot) {
Set<RoomCell> visited = new HashSet<>(); // Fresh for every room, even on a reused Solution.
cleanFrom(robot, 0, 0, 0, visited); // The unknown starting cell is our relative origin.
}
private void cleanFrom(Robot robot, int row, int col, int direction, Set<RoomCell> visited) {
visited.add(new RoomCell(row, col)); // Keep this mark permanently: this cell is now discovered.
robot.clean(); // Entry occurs once per reachable cell, so cleaning also occurs once.
for (int attempt = 0; attempt < 4; attempt++) {
int nextDirection = (direction + attempt) % 4; // Robot already faces this heading here.
int nextRow = row + ROOM_DIRECTIONS[nextDirection][0];
int nextCol = col + ROOM_DIRECTIONS[nextDirection][1];
RoomCell next = new RoomCell(nextRow, nextCol);
// Short-circuit first: do NOT move physically into an already discovered cell.
if (!visited.contains(next) && robot.move()) {
cleanFrom(robot, nextRow, nextCol, nextDirection, visited); // Explore the new cell.
goBack(robot); // A Java return did not move the robot: restore its parent cell.
}
robot.turnRight(); // Also turn after a wall or visited-cell skip; try the next heading.
}
// Four right turns restore the entry heading; every successful child move was undone.
}
private void goBack(Robot robot) {
robot.turnRight();
robot.turnRight(); // Face the parent: 180 degrees from the child's entry heading.
if (!robot.move()) throw new IllegalStateException("The return edge must remain open");
robot.turnRight();
robot.turnRight(); // At the parent, face toward the child again, ready for the loop's turn.
}
public static void main(String[] args) {
// Local smoke test: a one-cell room. The judge supplies a real Robot.
Robot singleCell = new Robot() {
private int heading = 0; // Hidden test state: 0=up, 1=right, 2=down, 3=left.
public boolean move() { return false; } // Every direction meets a wall.
public void turnLeft() { heading = (heading + 3) % 4; }
public void turnRight() { heading = (heading + 1) % 4; }
public void clean() { System.out.println("Cleaned the only cell."); }
};
new Solution().cleanRoom(singleCell); // Expected output: Cleaned the only cell. (once)
}
}The local invocation prints Cleaned the only cell. once. It returns no count. Each cleanRoom invocation has a new discovered set, so reusing the same Solution for another room does not carry old coordinates into the new search.
Why the condition is in this order
!visited.contains(next) && robot.move() uses Java’s short-circuit AND. If next is already discovered, the robot never moves into it.
Reversing the operands can move the robot into a known cell and then skip recursion. Without a corresponding physical return, subsequent relative coordinates would describe the wrong position.
Why goBack needs four turns
Suppose we moved right from parent S to child B. The child returns at B still facing right:
| Action | Physical cell | Heading |
|---|---|---|
| Child finishes | B | Right |
| First right turn | B | Down |
| Second right turn | B | Left, toward S |
| Move forward | S | Left |
| Third right turn | S | Up |
| Fourth right turn | S | Right, the branch heading |
| Parent loop’s separate right turn | S | Down, the next heading to try |
The four turns inside goBack restore the branch heading, not necessarily the parent’s original entry heading. The loop’s separate turn then selects the next branch.
The return move follows an edge that just succeeded in the opposite direction. With fixed walls, it must be open. The defensive exception in the example makes a violated API/room assumption visible instead of silently corrupting the search.
Dry run: separate Java frames from physical movement
Our first example has three open cells:
Hidden room (for the reader/test robot only):
column 0 column 1
row 0 S (start) B (open)
row 1 C (open) # (wall)
Start: S, facing up.
Right branch: S → B → physically back to S.
Down branch: S → C → physically back to S.S, B and C are names for physical cells in this example. Their relative coordinates are (0,0), (0,1) and (1,0). The solution never receives these names or the displayed matrix.

Read the text transcript
Follow the Java, step by step
Example: hidden room = [[1,1],[1,0]], start = (0,0), heading = up
What to track: S=(0,0), B=(0,1), C=(1,0). Each Java frame owns row, col, direction and attempt; the physical robot is shared. The complete three-cell traversal below groups each leaf’s four attempts. The solution does not receive the displayed room matrix.
-
Enter and clean S
Java operationvisited.add(new RoomCell(row, col));Statephysical pose: S, up; frame: row=0, col=0, direction=0; visited={S}; clean calls=1robot.clean follows the discovery mark. Relative (0,0) names the starting cell; it is not read from a hidden map.
-
Probe up: there is a wall
Java operationif (!visited.contains(next) && robot.move())Stateattempt=0; nextDirection=0; next=(-1,0); move returns false; physical pose remains S, upThe prospective coordinate is new, but the physical move fails. No child call and no goBack occur.
-
Turn even after the failed probe
Java operationrobot.turnRight();Statephysical pose: S, right; next loop attempt=1, nextDirection=1The turn keeps the physical heading aligned with the next direction number. Calculating that number alone would not turn the robot.
-
Move right and enter B
Java operationcleanFrom(robot, nextRow, nextCol, nextDirection, visited);Statemove succeeds to B; child frame: row=0, col=1, direction=1; visited={S,B}; clean calls=2The parent S frame pauses at attempt=1. B is physically occupied and faces right when its new frame starts.
-
Finish B’s four attempts
Java operationif (!visited.contains(next) && robot.move())StateB probes right: wall; down: wall; left: S already visited, no move call; up: wall. Four loop turns leave it at B facing rightThe visited check short-circuits the move toward S. After all attempts, B returns in its own entry pose—not in its parent’s cell.
-
Physically restore the parent
Java operationgoBack(robot);Statebefore: B, right. Turn twice→left; move→S; turn twice→right. After: S, rightJava has resumed the S frame, but only these API calls move the robot back. S remains discovered; it is not cleaned again.
-
Prepare the down branch
Java operationrobot.turnRight();Statephysical pose: S, down; parent frame still has direction=0; next attempt=2 computes nextDirection=2goBack restored the right branch heading. This separate loop turn chooses down for the next attempt.
-
Move down and enter C
Java operationcleanFrom(robot, nextRow, nextCol, nextDirection, visited);Statemove succeeds to C; child frame: row=1, col=0, direction=2; visited={S,B,C}; clean calls=3The discovered set is shared across both branches. It still contains B after that earlier call returned.
-
Finish C’s four attempts
Java operationif (!visited.contains(next) && robot.move())StateC probes down: wall; left: wall; up: S already visited, no move call; right: wall. Four loop turns leave it at C facing downIts clockwise order starts from its own entry heading, down—not from up. A leaf still makes all four loop turns.
-
Return from C and prepare left
Java operationgoBack(robot);StateC, down → turn twice to up → move to S → turn twice to down. The loop’s following right turn leaves S facing leftKeep physical restoration and the loop turn separate. Combining or omitting turns would make the next coordinate calculation disagree with the heading.
-
Probe the final root direction
Java operationif (!visited.contains(next) && robot.move())StateS frame: attempt=3; nextDirection=3; next=(0,-1); wall probe fails; pose remains S, leftThis is a failed probe, not a new visited cell. There is no child and no reverse movement.
-
Restore the root heading and finish
Java operationrobot.turnRight();Statephysical pose: S, up; visited={S,B,C}; clean calls=3; successful movements=4; right turns=20The fourth root loop turn restores up. The root exits with no integer result; cleaning is the externally visible effect.
Final result: S, B and C cleaned once each; 4 successful movements; 20 right turns; robot back at S facing up. cleanRoom returns void.
What is waiting on the call stack?
While B is being explored, Java has a paused S frame underneath B. S remembers row=0, col=0, direction=0 and attempt=1.
When B’s method returns, Java resumes S at goBack(robot). The physical robot is still at B. Only goBack moves it back to S. This is why a normal recursion return is not enough.
Our full three-cell run cleans 3 cells, makes 4 successful movements, and makes 20 right turns. The executable regression tests check these counts and the final cell/heading. Failed wall probes are not successful movements.
Why it works
Initialization
At the first call, the physical starting cell is the chosen relative origin and the robot faces direction 0. The discovered set is empty. Marking and cleaning this cell establishes the search state.
Maintenance
Before each loop attempt, the robot is in the frame’s own cell and faces nextDirection.
- A known neighbor is skipped without moving.
- A wall probe fails without changing position or heading.
- A successful new move enters a child with matching coordinates and heading. The child’s promise restores its own entry pose;
goBackrestores the parent cell and branch heading.
The one loop turn then establishes the heading for the following attempt. Four attempts restore the frame’s entry heading.
Coverage and termination
Every entered coordinate is marked before its neighbors are explored, so a cycle cannot create another entry for that cell. There are only A reachable cells, so at most A calls enter new cells.
If an open reachable cell remained undiscovered, consider a path from the start to it. At the first undiscovered cell on that path, its discovered predecessor would try the connecting direction. The move would succeed and create its child—a contradiction. Therefore every reachable cell is cleaned.
Cleaning occurs only on entry, which happens once per discovered cell. Returning through a previously cleaned cell does not create another entry or another clean call.
Complexity and alternative approaches
Let A be the number of reachable open cells, not the total rectangle area or the number of walls. Treat each Robot API call as constant time and HashSet operations as expected constant time.
- Time: O(A), expected. Each discovered cell performs four neighbor checks. Each DFS discovery edge is traversed once into the child and once back.
- Extra space: O(A). The discovered set holds A coordinate keys, and the recursive stack can contain up to A waiting frames in a long passage.
There are exactly A clean calls and 2(A−1) successful movements for this implementation. Its four loop turns per cell and four return turns per discovery edge total 8A−4 right turns. These counts explain the linear work; they do not claim the physically shortest possible cleaning route.
Any correct cleaner needs at least A clean calls. The asymptotic work is therefore optimal under these cost assumptions, even though travel distance or turning energy could be optimized for a different objective.
| Approach | Time | Extra space | Tradeoff |
|---|---|---|---|
| Enumerate simple routes, using only route-local expansion marks | O(4^A), loose bound | O(A) | Correct with physical restoration, but revisits areas through many routes. |
| Recursive DFS with permanent discovery marks | O(A), expected | O(A) | Simple call structure; must restore the real robot’s pose. |
| Explicit-frame DFS | O(A), expected | O(A) | Avoids Java recursion-depth limits, but must store the neighbor cursor and perform the same physical returns. |
BFS is not inherently wrong, but a queue cannot teleport this robot to a distant frontier cell. It would need a discovered map and navigation between queued cells. Logical graph-processing cost alone does not account for those physical movements. For this task, DFS naturally keeps the next action beside the robot’s current position.
Java does not guarantee enough recursion depth for every possible long passage. An explicit-frame implementation is the appropriate alternative when that limit matters; the position-and-heading invariant remains the same. Only the maintained recursive Java solution is shown here.
Common mistakes
- Reading the matrix from the example. It belongs to the hidden test environment, not the
cleanRoomarguments. - Removing discovered marks after returning. That is useful when enumerating routes, but here it repeats exploration and can repeat cleaning.
- Turning only after successful moves. After a wall or known-cell skip, the next calculated direction would no longer match the robot’s heading.
- Using a fixed direction order unrelated to the current frame’s heading. A child may enter facing right, down or left, not always up.
- Moving before checking the discovered set. A short-circuit skip can then leave the robot in a different cell without a child call or return move.
- Treating method return as physical backtracking. Returning restores control flow;
goBackrestores the position. - Turning twice, moving back, then stopping. The robot is at the correct parent cell but faces the wrong way. Restore the branch heading too.
- Using a coordinate encoding that assumes a known room width. A value-based coordinate key works with negative relative positions and needs no width guess.
Takeaway
Think in three pieces: a logical coordinate, a facing direction, and a set of discovered cells. Then make one promise precise: each recursive call returns in the cell and heading where it began.
When you can explain why the visited check happens before moving, why the loop turns unconditionally, and what the robot does during goBack, you can derive the code rather than memorizing its turns.
References
- LeetCode 489: Robot Room Cleaner — original problem and public metadata; its full statement is Premium.
- Hello Interview: Robot Room Cleaner — educational-layout reference. The Java, teaching examples, dry run and reasoning here are original Atlas material; no company timeline or frequency claims are copied.