Skip to main content
Talentd

Robot Room Cleaner - Solution & Explanation

HardPremiumFree on FleetCodeBacktrackingInteractive10 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

You are controlling a robot that is located somewhere in a room. The room is modeled as an m x n binary grid where 0 represents a wall and 1 represents an empty slot.

The robot starts at an unknown location in the room that is guaranteed to be empty, and you do not have access to the grid, but you can move the robot using the given API Robot.

You are tasked to use the robot to clean the entire room (i.e., clean every empty cell in the room). The robot with the four given APIs can move forward, turn left, or turn right. Each turn is 90 degrees.

When the robot tries to move into a wall cell, its bumper sensor detects the obstacle, and it stays on the current cell.

Design an algorithm to clean the entire room using the following APIs:

interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is obstacle and robot stays on the current cell.
  boolean move();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  // Clean the current cell.
  void clean();
}

Note that the initial direction of the robot will be facing up. You can assume all four edges of the grid are all surrounded by a wall.

 

Custom testing:

The input is only given to initialize the room and the robot's position internally. You must solve this problem "blindfolded". In other words, you must control the robot using only the four mentioned APIs without knowing the room layout and the initial robot's position.

 

Example 1:

Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

Example 2:

Input: room = [[1]], row = 0, col = 0
Output: Robot cleaned all rooms.

 

Constraints:

  • m == room.length
  • n == room[i].length
  • 1 <= m <= 100
  • 1 <= n <= 200
  • room[i][j] is either 0 or 1.
  • 0 <= row < m
  • 0 <= col < n
  • room[row][col] == 1
  • All the empty cells can be visited from the starting position.

Approach Overview

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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with BacktrackingO(n)O(n)Best approach when the grid is unknown and you must explore using robot movement APIs.
Graph Traversal with Coordinate MappingO(n)O(n)Useful mental model for mapping discovered cells while performing DFS exploration.

Video Solution

ROBOT ROOM CLEANER | LEETCODE # 489 | PYTHON BACKTRACK SOLUTION • Cracking FAANG • 20,049 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Robot Room Cleaner easy or hard?
Robot Room Cleaner is classified as Hard on LeetCode. The difficulty comes from controlling the robot using limited APIs, tracking orientation, and implementing correct backtracking so the robot returns to the previous cell after exploring each branch.
Robot Room Cleaner Python/Java solution
Implement DFS with backtracking using a visited set and direction vectors. In Python, a set of coordinate tuples works well, while Java typically uses a HashSet of encoded positions. Both versions maintain the robot's direction, rotate after each attempt, and perform a reverse move when returning from recursion.
How to solve Robot Room Cleaner in O(n)?
Use DFS exploration with a visited set storing coordinates relative to the starting cell. From each position, attempt to move in four directions. If the robot successfully moves to an unvisited cell, recursively explore it, then backtrack by reversing the move and restoring orientation. This ensures each cell is processed once.
What is the best approach for Robot Room Cleaner?
The best approach is DFS with backtracking. The robot explores all four directions from each cell, tracks visited coordinates in a set, and backtracks after exploring a branch to restore its previous position and orientation. This guarantees every reachable cell is cleaned exactly once with O(n) time and O(n) space.
Is Robot Room Cleaner asked at Google/Amazon/Meta?
Robot Room Cleaner is a classic hard interview problem commonly associated with Google and other large tech companies. It tests graph traversal, backtracking, and the ability to manage state when interacting with an external API rather than direct data structures.
What data structure is used in Robot Room Cleaner?
The core data structure is a hash set storing visited coordinates such as (row, col). This prevents revisiting cells and avoids infinite loops. Direction arrays and recursion stack frames are also used to manage traversal order and backtracking.
What is the time complexity of Robot Room Cleaner?
The time complexity is O(n), where n is the number of reachable cells. Each cell is visited once and the robot attempts up to four movements from that cell. Because each movement and backtrack operation is constant time, the total runtime scales linearly with the explored area.

Ready to solve this problem?

Practice Robot Room Cleaner with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Path Cost in a Hidden Grid

Next

Number of Spaces Cleaning Robot Cleaned