We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Robot Room Cleaner

Number: 865

Difficulty: Hard

Paid? Yes

Companies: Meta, LinkedIn, Google, Amazon, Citadel, Microsoft

Problem Description

A robot is placed in an unknown room modeled as an m x n grid with walls and open spaces. You can control the robot with an API that lets it move forward, turn left/right, and clean the current cell. Initially facing up, the robot must clean all accessible cells, navigating based only on success or failure responses from its move actions. The challenge is to backtrack and explore the entire room without knowledge of the layout.

Key Insights

  • Use DFS/backtracking to explore all directions from each cell.
  • Represent cells with relative coordinates because the room layout is unknown.
  • Maintain a visited set to avoid re-cleaning the same cell.
  • After moving to a new cell, backtrack (rotate 180 degrees, move, then re-adjust orientation).
  • Try all 4 directions with consistent relative adjustments (up, right, down, left).

Space and Time Complexity

Time Complexity: O(m * n) in the worst case where every cell is accessible. Space Complexity: O(m * n) due to the recursive stack and visited set.

Solution

We use a DFS/backtracking strategy to clean all reachable cells. Starting from the robot's initial location (assumed as coordinate (0, 0) in our relative system), we clean the current cell and mark it as visited. Then, for each of the 4 directions, we check if the robot can move into an unvisited cell. If the move is successful, we recursively clean from that new position. After exploring from the cell, we backtrack by turning 180 degrees, moving forward (to get back to the previous cell), and then turning 180 degrees again to reset the direction. This process is repeated for each cell until all accessible cells are cleaned. Key data structures include a set for tracking visited coordinates and an array representing the possible direction vectors.

Code Solutions

# DFS/backtracking solution for the Robot Room Cleaner problem

class Solution:
    def cleanRoom(self, robot):
        # Directions: Up, Right, Down, Left represented as (row, col) deltas.
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        
        # Set to keep track of visited cells using relative coordinates (row, col)
        visited = set()
        
        def go_back():
            # Reverse the movement: Turn 180 degrees, move forward, then turn 180 degrees again.
            robot.turnLeft()
            robot.turnLeft()
            robot.move()
            robot.turnLeft()
            robot.turnLeft()
        
        def dfs(row, col, cur_dir):
            # Mark the current cell as visited and clean it.
            visited.add((row, col))
            robot.clean()
            
            # Explore all four directions starting from current orientation.
            for i in range(4):
                new_dir = (cur_dir + i) % 4
                d_row, d_col = directions[new_dir]
                new_row, new_col = row + d_row, col + d_col
                
                # If new cell is not visited, try moving into it.
                if (new_row, new_col) not in visited:
                    if robot.move():
                        # Recursively explore from the new cell.
                        dfs(new_row, new_col, new_dir)
                        # Backtrack: move back to the previous cell.
                        go_back()
                
                # Turn the robot to the right to check the next direction.
                robot.turnRight()
        
        # Start DFS from the initial position (0, 0) and facing up (direction index 0).
        dfs(0, 0, 0)
← Back to All Questions