Robot Room Cleaner - Practice Coding Problems

Robot Room Cleaner - Problem

Backtracking Interactive Hard

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:

boolean move() - 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.
void turnLeft() - Robot will stay on the same cell after calling turnLeft/turnRight. Each turn will be 90 degrees.
void turnRight() - Robot will stay on the same cell after calling turnLeft/turnRight. Each turn will be 90 degrees.
void clean() - Clean the current cell.

Note: 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.

Input & Output

Example 1 — Small Room

$ 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

💡 Note: Robot starts at (1,3) and systematically visits all connected empty cells using DFS backtracking

Example 2 — Single Cell

$ Input: room = [[1]], row = 0, col = 0

› Output: Robot cleans the only cell

💡 Note: Trivial case: robot cleans current cell, no moves possible, algorithm terminates

Example 3 — L-shaped Room

$ Input: room = [[1,1,0],[1,1,1],[0,0,1]], row = 0, col = 0

› Output: Robot cleans all 5 reachable cells

💡 Note: Robot navigates L-shape by exploring all directions and backtracking when blocked

Constraints

m == room.length
n == room[i].length
1 ≤ m, n ≤ 100
room[i][j] is either 0 or 1
All the empty cells can be visited from the starting position

Visualization

Tap to expand

Understanding the Visualization

Unknown Room

Robot starts at unknown position in binary grid

API Exploration

Use move(), turnLeft(), turnRight(), clean() to navigate

Complete Cleaning

Every reachable cell must be cleaned exactly once

Key Takeaway

🎯 Key Insight: Use systematic DFS backtracking with relative coordinates to ensure complete coverage without grid access

Asked in

f Facebook 45 G Google 38 a Amazon 25 M Microsoft 20

The key insight is to use DFS backtracking with relative coordinate tracking to systematically explore every reachable cell exactly once. The optimal approach uses a visited set and four-directional exploration with backtracking. Time: O(N), Space: O(N) where N is the number of empty cells.

Common Approaches

Approach	Time	Space	Notes
✓ Random Exploration	O(∞)	O(1)	Move randomly in available directions until no progress can be made
Systematic DFS Backtracking	O(N)	O(N)	Use DFS with backtracking to systematically visit every reachable cell exactly once

Random Exploration — Algorithm Steps

Step 1: Clean current cell
Step 2: Try random directions until one works
Step 3: Move and repeat until stuck

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Robot begins at unknown position

Random Move

Try random directions until one works

Problem

May miss cells or never complete

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct {
    int (*move)(void);
    void (*turnLeft)(void);
    void (*turnRight)(void);
    void (*clean)(void);
} Robot;

int mockMove() { return 0; }
void mockTurnLeft() {}
void mockTurnRight() {}
void mockClean() {}

void cleanRoom(Robot* robot) {
    robot->clean();
    srand(time(NULL));
    
    while (1) {
        int moved = 0;
        int directions[4] = {0, 1, 2, 3};
        
        // Simple shuffle
        for (int i = 3; i > 0; i--) {
            int j = rand() % (i + 1);
            int temp = directions[i];
            directions[i] = directions[j];
            directions[j] = temp;
        }
        
        for (int i = 0; i < 4; i++) {
            if (robot->move()) {
                cleanRoom(robot);
                // Go back
                robot->turnRight();
                robot->turnRight();
                robot->move();
                robot->turnRight();
                robot->turnRight();
                moved = 1;
                break;
            }
            robot->turnRight();
        }
        
        if (!moved) break;
    }
}

void solution(Robot* robot) {
    cleanRoom(robot);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    printf("null\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(∞)

May never terminate or take exponential time

✓ Linear Growth

Space Complexity

O(1)

No additional storage needed

✓ Linear Space

185.0K Views

Medium Frequency

~35 min Avg. Time

2.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Random Exploration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler