Your Dashboard
Interview Coaching
Learn
System Design
ML System Design
Code
Behavioral
Salary Negotiation
Interview Guides
Leetcode 489. Robot Room Cleaner
Control a robot with only move/turn/clean APIs to traverse and clean every reachable cell in an unknown grid with obstacles and no global map. The challenge is to explore the entire accessible area using DFS/backtracking while tracking visited coordinates and managing orientation to avoid revisiting or getting stuck.
Asked at:
Meta
DESCRIPTION
Control a robot with only move/turn/clean APIs to traverse and clean every reachable cell in an unknown grid with obstacles and no global map. The challenge is to explore the entire accessible area using DFS/backtracking while tracking visited coordinates and managing orientation to avoid revisiting or getting stuck.
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 cleans all reachable cells
Explanation: The robot starts at position (1,3) and explores the entire reachable area using DFS with backtracking. Cells with 0 are obstacles, cells with 1 are cleanable.
Constraints:
- 1 <= room.length <= 100
- 1 <= room[i].length <= 200
- room[i][j] is either 0 (obstacle) or 1 (cleanable)
- The robot starts in a cleanable cell
- All cleanable cells are connected (reachable from starting position)
- Robot APIs: move() returns boolean, turnLeft() and clean() return void
Understanding the Problem
Let's understand what we're being asked to do. We have a robot in an unknown grid with obstacles, and we can only use three APIs: move() (try to move forward), turnLeft() (rotate 90° left), and clean() (clean current cell).
The robot starts at some position facing some direction. We don't have a map, and we don't know the grid boundaries or obstacle locations ahead of time. We can only discover the environment by trying to move.
Key constraint: We must clean every reachable cell exactly once. The robot can't see the whole grid - it can only sense if the cell directly in front is blocked when it tries to move.
Edge cases to consider: What if the robot starts in a corner? What if there are isolated areas we can't reach? How do we avoid cleaning the same cell twice? How do we know when we've explored everything?
Building Intuition
Since we can't see the whole grid, we need to explore systematically by trying all four directions from each cell. When we hit a wall or visited cell, we backtrack to try other paths.
The challenge is: without a global map, how do we track which cells we've visited? We need to maintain relative coordinates based on our starting position and current orientation.
By tracking visited coordinates and our current direction, we can avoid revisiting cells even though we're exploring blindly. When we finish exploring all directions from a cell, we can backtrack to the previous cell and continue exploring.
This systematic exploration guarantees we'll visit every reachable cell exactly once, without getting stuck in loops.
Imagine exploring a dark maze with only a flashlight that shows one step ahead. You mark each room you enter with chalk.
From each room, you try all four doors. If a door leads to an unmarked room, you enter it and repeat. If all doors are blocked or lead to marked rooms, you retrace your steps back to the previous room and try other doors.
The key insight: even without seeing the whole maze, this systematic 'try all directions, backtrack when stuck' approach guarantees you'll explore everything reachable.
Common Mistakes
Optimal Solution
Use depth-first search with backtracking to explore the grid systematically. Track visited cells using relative coordinates (starting position as origin). From each cell, try all four directions: if a direction leads to an unvisited cell, move there recursively and explore. After exploring all directions, backtrack by moving back and restoring orientation. This ensures every reachable cell is visited exactly once.
Start robot room cleaner - clean all reachable cells using DFS
0 / 50
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(N - M) We visit each cleanable cell exactly once, where N is total cells and M is obstacles. Each cell involves 4 direction checks and constant work.
Space Complexity: O(N - M) The recursion stack depth equals the number of cells in the longest path from start to furthest cell. The visited set stores coordinates for all cleanable cells.
What We've Learned
- DFS with backtracking in physical space: When exploring unknown environments with limited APIs (no global map access), use DFS with explicit backtracking moves - after exploring a direction, physically return the robot to its previous position and orientation by reversing moves (turn 180°, move forward, turn 180° again) to maintain state consistency.
- Relative coordinate tracking without absolute reference: Track visited cells using a virtual coordinate system starting from (0,0) at the robot's initial position, updating coordinates based on current direction (use direction vectors: up=[0,1], right=[1,0], down=[0,-1], left=[-1,0]) - this allows obstacle detection and cycle prevention without knowing the actual grid layout.
- Direction state management with modular arithmetic: Maintain robot orientation as an integer index (0-3) into a direction array and use modulo operations for turns (right: `(dir + 1) % 4`, left: `(dir + 3) % 4` or `(dir - 1) % 4`) - this elegantly handles circular direction changes without complex conditional logic.
- Visited set for cycle prevention in exploration: Always use a set to track visited coordinates before attempting to move - checking `if neighbor not in visited and robot.move()` prevents infinite loops and redundant cleaning, crucial since the robot can't peek ahead and must attempt moves to discover obstacles.
- Systematic neighbor exploration pattern: Explore all four directions in a fixed clockwise/counterclockwise order (0°, 90°, 180°, 270°) from each cell, turning the robot after each attempt - this systematic approach ensures complete coverage and makes backtracking predictable, preventing missed cells in complex layouts.
- Backtracking in constrained API environments: When working with limited control APIs (can't teleport or query state), implement backtracking by storing the exact sequence of moves needed to return - in this case, the elegant solution is to always return to parent position after exploring each direction, maintaining the robot as a stateful explorer rather than treating it as a passive data structure.
Related Concepts and Problems to Practice
medium
Word Search uses DFS with backtracking on a 2D matrix to explore paths while tracking visited cells and reverting state, which is the exact same pattern as the robot cleaner problem. Both require exploring all reachable cells in a grid while managing state and avoiding revisits.
medium
Number of Islands involves DFS traversal on a 2D matrix to explore connected components while marking visited cells, similar to how the robot must traverse and clean all reachable cells. Both problems require systematic exploration of a grid structure with visited tracking.
Test Your Understanding
Why is matrix the right data structure for this problem?
matrix provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid October, 2025
Meta
Senior
Similar question presented as a mouse in a maze finding the cheese.
Late September, 2025
Meta
Mid-level
Late September, 2025
Meta
Staff
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.