Robot Room Cleaner

#21 Most AskedHard

Robot Room Cleaner #21 Most Asked

Hard

15 views

Topics:

ArraysRecursion

You are controlling a robot that is located somewhere in a room. The room is modeled as a grid of cells, where each cell can be free or blocked.

The robot can move forward, turn left, or turn right. When you command the robot to move forward, it moves one cell in the direction it is facing.

The robot cannot enter blocked cells.

Given the room in a grid format, your task is to clean all the free cells. The robot starts at an unknown location, facing up.

For simplicity, assume:

The room is rectangular and has no obstacles on the boundary.
The robot initial position is always a free cell.
The robot cleans the cell it is on after each move.
Assume the initial position of the robot is always (0, 0).

Interface:

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

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

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

Example:

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

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 (1, 3).
From that point, the robot can clean all accessible cells.

Note:

The input is only logically given. You need to write the implementation of the Robot class.
You are given the room in terms of a 2D grid, but you do not have access to the actual room directly.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the room (number of rows and columns), and what is the maximum size the room can be?
How is the room represented? Is it a 2D array or some other data structure, and what values represent a clean vs. an obstacle?
When the robot encounters an obstacle, should it attempt to move forward indefinitely, or is there a limit to the number of times it can attempt to move in the same direction before trying another direction?
Is the robot's initial position always guaranteed to be a clean cell, and do I need to ensure the robot returns to its starting position at the end?
If the room is already completely clean, what should the algorithm do?

Brute Force Solution

Approach

The robot needs to clean every room. The brute force method makes the robot try every possible path, moving forward, turning, and backtracking until it has explored everywhere it can possibly go. It's like trying every single maze solution until one works.

Here's how the algorithm would work step-by-step:

Start the robot at its initial position.
Make the robot move forward one step if it can.
If it hits a wall, make it turn to the right.
After turning right, try moving forward again.
If it still can't move forward after turning, make it turn right again, and repeat until it has turned all the way around.
If it has turned all the way around and still can't move, make it backtrack one step to where it came from.
Keep track of all the rooms the robot has visited to avoid cleaning the same room twice unnecessarily.
Continue these steps until the robot has no more unvisited rooms to reach and cannot move anywhere new.

Code Implementation

def robot_room_cleaner_brute_force(robot): 
    visited_cells = set()
    current_direction = 0  # 0: up, 1: right, 2: down, 3: left
    current_row = 0
    current_col = 0

    def move_forward():
        nonlocal current_row, current_col
        if current_direction == 0:
            current_row -= 1
        elif current_direction == 1:
            current_col += 1
        elif current_direction == 2:
            current_row += 1
        else:
            current_col -= 1

    def move_back():
        nonlocal current_row, current_col
        if current_direction == 0:
            current_row += 1
        elif current_direction == 1:
            current_col -= 1
        elif current_direction == 2:
            current_row -= 1
        else:
            current_col += 1

    def get_current_cell():
        return (current_row, current_col)

    while True:
        current_cell = get_current_cell()
        if current_cell not in visited_cells:
            robot.clean()
            visited_cells.add(current_cell)

        can_move_forward = robot.move()

        if can_move_forward:
            move_forward()
            continue
        else:
            # Try all directions by turning right
            turned_count = 0
            while turned_count < 4:
                robot.turn_right()
                current_direction = (current_direction + 1) % 4
                turned_count += 1
                can_move_forward = robot.move()

                if can_move_forward:
                    move_forward()
                    break

            # If we can't move anywhere, backtrack
            if turned_count == 4:
                move_back()

                robot.turn_right()
                robot.turn_right()
                if not robot.move():
                  break
                move_forward()
                robot.turn_right()
                robot.turn_right()

        all_cleaned = True
        for row_delta in range(-10, 11):
            for col_delta in range(-10, 11):
                test_row = current_row + row_delta
                test_col = current_col + col_delta
                if (test_row, test_col) not in visited_cells and robot.is_valid_move(row_delta, col_delta):
                    all_cleaned = False
                    break
            if not all_cleaned:
                break

        if all_cleaned and not can_move_forward:
            break

    return list(visited_cells)

Big(O) Analysis

Time Complexity

O(n) – The robot explores each reachable room at most a constant number of times (due to backtracking and turning). The input size, n, represents the number of reachable rooms in the grid. Since each room is visited a limited number of times, the total number of operations grows linearly with the number of rooms. Thus, the time complexity is O(n).

Space Complexity

O(N) – The algorithm keeps track of all visited rooms to avoid redundant cleaning. This implies using a data structure, such as a set or hash map, to store the coordinates of each visited room. In the worst-case scenario, the robot might need to visit every room in the environment. Therefore, if we consider N to be the number of rooms in the environment, the space complexity is proportional to the number of visited rooms, resulting in O(N) space complexity.

Optimal Solution

Approach

The problem involves simulating a robot cleaning a room. Instead of exhaustively exploring every possible path, the efficient solution relies on a depth-first search strategy combined with backtracking to systematically explore the room and ensure complete cleaning.

Here's how the algorithm would work step-by-step:

Imagine the robot starts at a known location and direction.
The robot tries to move forward. If it can't (because of a wall), it turns right.
If the robot *can* move forward, it cleans the current cell, marks it as visited, and then moves forward.
After moving forward, the robot repeats the process of trying to move in all directions.
Once the robot has tried all four directions from its current location (meaning it's surrounded by visited cells or walls in every direction), it needs to go back to where it came from.
To go back, the robot turns around and moves forward. It keeps doing this until it finds a cell with unexplored directions.
The robot keeps exploring and backtracking until it returns to its starting position and has explored all possible paths. This guarantees the entire room has been cleaned.

Code Implementation

class Robot:
    def move(self): 
        return True
    def turn_left(self): 
        return
    def turn_right(self): 
        return
    def clean(self): 
        return

def clean_room(robot):
    visited = set()
    # Directions: up, right, down, left
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    def go_back():
        robot.turn_right()
        robot.turn_right()
        robot.move()
        robot.turn_right()
        robot.turn_right()

    def explore(row, col, current_direction):
        visited.add((row, col))
        robot.clean()

        for index in range(4):
            new_direction = (current_direction + index) % 4
            new_row = row + directions[new_direction][0]
            new_col = col + directions[new_direction][1]

            #Avoid exploring already cleaned or obstacle cells
            if (new_row, new_col) not in visited:
                robot.turn_right()

                if robot.move():
                    # Explore in the new direction.
                    explore(new_row, new_col, new_direction)
                    # Backtrack after exploring the new direction.
                    go_back()

    explore(0, 0, 0)

Big(O) Analysis

Time Complexity

O(n) – The algorithm essentially visits each cell in the room at most a constant number of times. n represents the number of cells in the room. The robot explores each cell, cleans it, and backtracks when necessary. Each cell's four directions are checked, but that's a constant factor. Therefore, the time complexity is directly proportional to the number of cells, making it O(n).

Space Complexity

O(N) – The space complexity is dominated by the recursion depth and the visited set. The maximum recursion depth corresponds to the longest path the robot can take without revisiting a cell. In the worst-case scenario, the robot may need to visit all N cells in the room before returning to the starting position, leading to a recursion depth of O(N). Additionally, we store visited cells in a set to avoid re-cleaning. This set can grow to a size proportional to the number of cells, also O(N). Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty room (no cells)	The base case for the recursion should immediately return, avoiding any processing.
Room with a single cell	The robot cleans it and returns without any further movements.
Room is a straight line (1xn or nx1)	The algorithm should handle this by moving along the line, cleaning each cell, and turning around at the end if necessary.
Room is a fully walled-in space (no exits)	The robot might get stuck in the initial cell if it cannot move, requiring a check for this and immediate termination.
Robot starts in a dirty cell with no cleanable adjacent cells	The robot cleans the current cell and algorithm will backtrack immediately as there is nowhere else to go.
Circular room layout where returning to the starting cell doesn't indicate full exploration	Maintain a set of visited cells to avoid infinite loops and ensure full exploration, regardless of cyclic paths.
Integer overflow in distance calculations (if applicable)	Use appropriate data types to prevent overflow (e.g., long) or ensure calculations are done in a way that prevents overflow.
Maximum recursion depth exceeded for very large rooms	While unlikely given reasonable room sizes, consider iterative solution instead of recursive or implement tail-call optimization.

Null or empty room (no cells)

How to Handle:

The base case for the recursion should immediately return, avoiding any processing.

Room with a single cell

How to Handle:

The robot cleans it and returns without any further movements.

Room is a straight line (1xn or nx1)

How to Handle:

The algorithm should handle this by moving along the line, cleaning each cell, and turning around at the end if necessary.

Room is a fully walled-in space (no exits)

How to Handle:

The robot might get stuck in the initial cell if it cannot move, requiring a check for this and immediate termination.

Robot starts in a dirty cell with no cleanable adjacent cells

How to Handle:

The robot cleans the current cell and algorithm will backtrack immediately as there is nowhere else to go.

Circular room layout where returning to the starting cell doesn't indicate full exploration

How to Handle:

Maintain a set of visited cells to avoid infinite loops and ensure full exploration, regardless of cyclic paths.

Integer overflow in distance calculations (if applicable)

How to Handle:

Use appropriate data types to prevent overflow (e.g., long) or ensure calculations are done in a way that prevents overflow.

Maximum recursion depth exceeded for very large rooms

How to Handle:

While unlikely given reasonable room sizes, consider iterative solution instead of recursive or implement tail-call optimization.