2061. Number of Spaces Cleaning Robot Cleaned

MediumArrayMatrixSimulation
Leetcode Link

Problem Description

The given problem is about simulating the path of a cleaning robot inside a room. The room is represented as a 0-indexed 2D binary matrix room where a 0 indicates an empty space that can be cleaned, and a 1 indicates a space with an object that cannot be passed through. The robot starts at the top left corner of the matrix, which is guaranteed to be an empty space (a 0), and initially moves right.

The behavior of the robot is very specific: it proceeds straight until it either hits an object (a 1 in the matrix) or it reaches the edge of the room. Upon encountering an obstruction or the edge, the robot turns 90 degrees clockwise and continues in the new direction. Importantly, any empty space the robot passes over is considered "cleaned," including the starting space.

The problem asks for the total number of unique spaces that the robot cleans if it moves indefinitely following these rules.

Intuition

The key to solving this problem is to simulate the movement of the robot and keep track of the spaces it cleans. We need a way to mark the spaces the robot visits as cleaned, prevent re-cleaning the same space, and we want to ensure the robot turns appropriately when required.

To solve this problem, we can perform a Depth-First Search (DFS) algorithm starting from the initial position of the robot. The DFS function can be implemented to take the current position (i, j) and the direction k the robot is facing as its parameters. We will clean the space if it's empty (represented by a 0), mark it as visited (to avoid re-cleaning), and then proceed in the current direction if the next space is also empty (a 0). If the robot encounters an object (a 1) or the edge of the room, it should turn 90 degrees clockwise, which can be implemented by updating the direction k.

For our DFS function, we keep track of "visited" states including positions and the current direction. This is important because the robot could potentially return to a position it has visited before but facing a different direction. We need to ensure we only count a space as clean when we visit it for the first time in the given direction.

We also keep a count of the cleaned spaces, incrementing it whenever we clean a new space. The DFS proceeds recursively, and we return the final count of cleaned spaces once the simulation is complete and there are no new spaces left to visit.

This approach works as the robot's path is deterministic, and by following the robot's rules, we can simulate its entire path until it either gets stuck in a loop or has cleaned all accessible spaces.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Solution Approach

The implementation of the solution uses the Depth-First Search (DFS) algorithm as its base approach to traverse through the room matrix. The algorithm deploys a recursive function dfs which takes the current position (i, j) and the current facing direction k as its parameters.

The algorithm uses several variables and a structure:

  • dir is a tuple (0, 1, 0, -1, 0) representing the directions in which the robot can move. Index k indicates the current direction. If k is 0, it means the robot moves to the right; if k is 1, it means moving down; if k is 2, moving left; and if k is 3, moving up.

  • vis is a set that keeps track of the visited positions and their associated directions. A position is deemed visited along with a specific direction, not just the positions itself.

  • ans is the accumulator counter that counts the number of unique spaces that have been cleaned.

Let's walk through the implementation details of the solution:

  1. We start off with our DFS function dfs(i, j, k).

    • If the position (i, j, k) is in vis, it means this space with the current direction was already processed, and we return immediately to avoid repeating work.
    • If the current space is clean (room[i][j] == 0), we increment ans to denote a new clean space, and we mark the space as visited by setting room[i][j] to -1.
    • The current state (i, j, k) is added to the vis set to mark it as visited.
    • The robot then tries to move in the direction k. If the next position is within the bounds of the matrix and is empty, the robot moves to it, and dfs is called recursively.
    • If the robot encounters an obstruction or the edge, it turns 90 degrees clockwise by incrementing k (k + 1) % 4, and dfs is called recursively without changing the position but only changing the direction.

  2. The initial call to dfs(0, 0, 0) begins the simulation with the robot starting in the upper left corner and facing right.

  3. The dfs function will continue to recurse, simulating the robot's movement until all cleanable spaces are visited.

  4. Eventually, the program will run out of new spaces to visit. At this point, all spaces that could be cleaned by the robot following the rules have been counted, and the final ans value denotes this count.

This recursive algorithm with the direction and visited tracking elegantly simulates the robot's movement and provides us with the correct count of uniquely cleaned spaces. The solution works efficiently within the constraints specified in the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's consider a small room room with the following scenario to illustrate the solution approach:

1[
2  [0, 0, 1],
3  [0, 1, 0],
4  [0, 0, 0]
5]

In this room matrix, 0 denotes an empty and cleanable space, while 1 represents an obstacle the robot can't pass through.

We will simulate the robot's movement starting from the top-left corner (0, 0), initially moving right (direction k = 0).

  1. The robot starts at (0, 0) which is empty, and we perform dfs(0, 0, 0). The space is counted as cleaned (ans = 1), and the position (0, 0, 0) is marked as visited.

  2. The robot moves right to (0, 1) following its rightward direction. Another dfs(0, 1, 0) is called. The empty space is cleaned (ans = 2), and (0, 1, 0) is marked as visited.

  3. The robot tries to move right again but encounters a wall (room[0][2] == 1). It can't proceed, so it turns 90 degrees clockwise and faces down (k = 1).

  4. Now facing down, the robot moves to (1, 1) since the space below the starting point (0, 0) is an obstacle. We perform dfs(1, 1, 1). (1, 1, 1) is marked as visited, and since we encountered another obstacle at (1, 1), the robot turns 90 degrees clockwise again (k = 2).

  5. Facing left (k = 2), the robot moves to (1, 0) and we call dfs(1, 0, 2). The space is cleanable, so ans is updated (ans = 3), and (1, 0, 2) is marked as visited.

  6. Since (0, 0) has been visited from the right, the robot will move left another space to (2, 0). This clean space updates ans (ans = 4), and (2, 0, 2) is marked as visited.

  7. Continuing left would hit the matrix bound, so the robot turns clockwise, now facing up (k = 3), but this is blocked by an obstacle. Clockwise again (k = 0), this next space is (2, 1), but it's blocked too, so it turns clockwise (k = 1).

  8. Now facing down, the robot can move into (2, 1) and perform dfs(2, 1, 1), cleaning this space (ans = 5), and marking (2, 1, 1) as visited.

  9. Next, it advances to (2, 2) and calls dfs(2, 2, 1), cleans it (ans = 6), and marks (2, 2, 1) as visited. This is the last horizontal line where the robot can move without obstacles, so it continues right until it hits the boundary, turns clockwise to face up (k = 3), and moves back.

  10. On moving up, at (1, 2), it can't move right, left, or up since either the space is an obstacle or has been visited from that direction already. The robot is stuck in a loop.

The system comes to a halt when there are no new spaces to be visited. The answer, ans, is 6, which represents the total number of unique cleanable spaces in the room.

Solution Implementation

1class Solution:
2    def numberOfCleanRooms(self, room):
3        # Inner recursive function to perform depth-first search
4        def dfs(row, col, direction):
5            # If this state has been visited before, do nothing
6            if (row, col, direction) in visited:
7                return
8          
9            # If the current room is clean, increment the counter
10            nonlocal clean_rooms_count
11            clean_rooms_count += room[row][col] == 0
12
13            # Mark this room as visited by setting its value to -1
14            room[row][col] = -1
15
16            # Add the current state to the visited set
17            visited.add((row, col, direction))
18
19            # Calculate the next room's coordinates based on the direction
20            next_row, next_col = row + directions[direction], col + directions[direction + 1]
21
22            # If the next room is within bounds and not a wall (room value != 1), move to it
23            if 0 <= next_row < len(room) and 0 <= next_col < len(room[0]) and room[next_row][next_col] != 1:
24                dfs(next_row, next_col, direction)
25            else:
26                # If there's a wall, change direction (rotate right)
27                dfs(row, col, (direction + 1) % 4)
28
29        # Set to keep track of visited states (row, col, direction)
30        visited = set()
31      
32        # Directions correspond to right (0, 1), down (1, 0), left (0, -1), up (-1, 0)
33        # The directions are intentionally shifted by one to facilitate indexing. This means that
34        # directions[i] gives the row offset and directions[i+1] gives the column offset.
35        directions = [0, 1, 0, -1, 0]
36
37        # Counter for the number of clean rooms visited
38        clean_rooms_count = 0
39
40        # Start the DFS from the top-left corner of the room facing right (direction is 0)
41        dfs(0, 0, 0)
42
43        # Return the total count of clean rooms visited
44        return clean_rooms_count
45
1class Solution {
2    private boolean[][][] visited;
3    private int[][] room;
4    private int cleanRoomsCount;
5
6    // Counts the number of clean rooms that the robot cleans
7    public int numberOfCleanRooms(int[][] room) {
8        // The visited array tracks the cells visited for each of the 4 directions
9        visited = new boolean[room.length][room[0].length][4];
10        this.room = room; // Initialize room reference
11        cleanRoomsCount = 0; // Initialize clean rooms count
12      
13        dfs(0, 0, 0); // Start the DFS from the top-left corner in direction '0' (right)
14        return cleanRoomsCount; // Return the total number of clean rooms visited
15    }
16
17    // Performs DFS to navigate the room based on the given rules
18    private void dfs(int i, int j, int dir) {
19        // If current position and direction is already visited, do nothing
20        if (visited[i][j][dir]) {
21            return;
22        }
23
24        // Relative directions: right (0), down (1), left (2), up (3)
25        int[] directions = {0, 1, 0, -1, 0};
26      
27        // Mark the current position and direction as visited
28        visited[i][j][dir] = true;
29
30        // If current room is clean (i.e., not a wall or already counted), increment cleanRoomsCount
31        if (room[i][j] == 0) {
32            cleanRoomsCount++;
33            // Mark the room as cleaned by setting it to a distinct value (-1)
34            // to avoid recounting when visited from a different direction
35            room[i][j] = -1;
36        }
37
38        // Compute next position based on the current direction
39        int nextX = i + directions[dir];
40        int nextY = j + directions[dir + 1];
41
42        // Move to next position if it's within bounds and is not a wall
43        if (nextX >= 0 && nextX < room.length && nextY >= 0 && nextY < room[0].length && room[nextX][nextY] != 1) {
44            dfs(nextX, nextY, dir); // Continue in the same direction
45        } else { 
46            // If hitting a wall or out of bounds, turn right (increment direction)
47            // and continue DFS with the new direction. Use modulo to wrap direction.
48            dfs(i, j, (dir + 1) % 4);
49        }
50    }
51}
52
1#include <vector>
2#include <functional>
3#include <cstring>
4
5class Solution {
6public:
7    int numberOfCleanRooms(vector<vector<int>>& room) {
8        int m = room.size();    // Number of rows
9        int n = room[0].size(); // Number of columns
10        bool visited[m][n][4];  // 3D array to keep track of visited states
11        memset(visited, false, sizeof(visited)); // Initialize visited array to false
12
13        // Array that represents the directions we can move in the grid (right, down, left, up)
14        int directions[5] = {0, 1, 0, -1, 0};
15      
16        int cleanRoomsCount = 0; // Initialize count of clean rooms
17
18        // Lambda function that performs Depth-First Search (DFS) starting from (i, j) in direction k
19        function<void(int, int, int)> dfs = [&](int i, int j, int dirIndex) {
20            // If the current state has been visited, return
21            if (visited[i][j][dirIndex]) {
22                return;
23            }
24
25            // Mark the current cell as visited and clean it if it's not an obstacle
26            cleanRoomsCount += room[i][j] == 0;
27            room[i][j] = -1; // Mark the room as cleaned, indicating that it's been traversed
28            visited[i][j][dirIndex] = true; // Mark current state as visited
29
30            // Calculate the next cell coordinates by moving in the current direction
31            int nextX = i + directions[dirIndex];
32            int nextY = j + directions[dirIndex + 1];
33
34            // If the next cell is within bounds and not an obstacle, move to the next cell
35            if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && room[nextX][nextY] != 1) {
36                dfs(nextX, nextY, dirIndex);
37            } else {
38                // If we can't move forward, turn right (clockwise) and stay in the current cell
39                dfs(i, j, (dirIndex + 1) % 4); // % 4 to cycle through direction indices
40            }
41        };
42
43        dfs(0, 0, 0); // Start DFS from the top-left corner in the right direction
44        return cleanRoomsCount; // Return the total count of clean rooms
45    }
46};
47
1const DIRECTIONS: number[] = [0, 1, 0, -1, 0]; // Directions: right, down, left, up.
2
3let visited: boolean[][][]; // 3D array to keep track of visited states.
4let cleanRoomsCount: number = 0; // Count of clean rooms.
5
6function numberOfCleanRooms(room: number[][]): number {
7    const rows: number = room.length; // Number of rows in the room grid.
8    const cols: number = room[0].length; // Number of columns in the room grid.
9    visited = Array.from({length: rows}, () => Array.from({length: cols}, () => Array(4).fill(false)));
10
11    // Kick off the depth-first search (DFS) from the top-left corner of the room facing right.
12    dfs(0, 0, 0, room);
13    return cleanRoomsCount; // Return final count of cleaned rooms.
14}
15
16function dfs(row: number, col: number, dirIndex: number, room: number[][]): void {
17    // If the current state has already been visited, no need to proceed further.
18    if (visited[row][col][dirIndex]) {
19        return;
20    }
21
22    // If the current cell is not an obstacle, increment the clean rooms count.
23    if (room[row][col] === 0) {
24        cleanRoomsCount++;
25    }
26    // Mark the current cell visited and cleaned by indicating it's been traversed.
27    visited[row][col][dirIndex] = true;
28    room[row][col] = -1; // Indication of cleaned room.
29
30    // Calculate next cell's coordinates based on current direction.
31    const nextRow = row + DIRECTIONS[dirIndex];
32    const nextCol = col + DIRECTIONS[dirIndex + 1];
33
34    // Check if the next cell is within bounds and is not an obstacle.
35    if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && room[nextRow][nextCol] !== 1) {
36        dfs(nextRow, nextCol, dirIndex, room); // Move to the next cell in the same direction.
37    } else {
38        // If facing an obstacle or out of bounds, turn right (clockwise) without changing cell.
39        dfs(row, col, (dirIndex + 1) % 4, room); // % 4 cycles through the direction indices.
40    }
41}
42
43// Example usage:
44// console.log(numberOfCleanRooms([[0,0,0],[0,1,0],[0,0,0]])); // Possible room layout
45
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer technique does Quick Sort use?

Time and Space Complexity

The time complexity of the provided code is O(N * M) where N represents the number of rows and M represents the number of columns in the room grid. This is because in the worst-case scenario, the robot will visit each cell at most once in each direction before it finds itself in a previously visited state, leading to a visitation of all N * M cells in 4 directions.

The space complexity is also O(N * M) because we are using a set vis to store a tuple containing the coordinates and direction for each visited cell. In the worst case, each cell will be visited in all 4 directions, leading to 4 * N * M possible states that can be stored in the set. However, constants are dropped in Big O notation, leaving us with O(N * M).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫