LeetCode 2061 - Number of Spaces Cleaning Robot Cleaned

In this problem, we are given a 2D binary matrix called room. Each cell represents a position in the room: - 0 means the space is empty and can be cleaned. - 1 means the space contains an object and cannot be entered.

leetcodemediumarraymatrixsimulation

LeetCode Problem 2061

Difficulty: 🟡 Medium
Topics: Array, Matrix, Simulation

Solution

Problem Understanding

In this problem, we are given a 2D binary matrix called room. Each cell represents a position in the room:

  • 0 means the space is empty and can be cleaned.
  • 1 means the space contains an object and cannot be entered.

A cleaning robot starts at the top-left corner (0, 0), and the problem guarantees that this starting position is always empty.

The robot initially faces to the right. It follows a very strict movement rule:

  1. Move forward in the current direction as long as the next cell is valid and empty.
  2. If the next move would either:
  • go outside the room boundaries, or
  • hit an object (1),

then the robot does not move forward. Instead, it rotates 90 degrees clockwise and tries again.

The robot continues forever. Every empty space it visits becomes cleaned.

The task is to return the total number of unique spaces that become cleaned over the infinite execution of the robot.

The important detail is that the robot may enter a cycle. Since the robot runs indefinitely, eventually its state must repeat. Once the exact same state repeats, the robot will continue behaving identically forever, so no new spaces will ever be cleaned after that point.

The constraints are:

  • 1 <= m, n <= 300
  • The grid may contain up to 90,000 cells.
  • The robot can revisit cells many times.

These constraints tell us that we need an efficient simulation. A naive infinite simulation is impossible because the robot never stops by itself.

Several edge cases are important:

  • A room with only one cell.
  • A room where the robot immediately becomes trapped.
  • A room with no obstacles.
  • Situations where the robot revisits the same cell but with a different direction, because direction affects future movement.
  • Large rooms where repeated simulation without cycle detection would run forever.

Approaches

Brute Force Approach

The most straightforward idea is to simulate the robot indefinitely while tracking cleaned cells.

At every step:

  • Mark the current cell as cleaned.
  • Attempt to move forward.
  • If blocked, rotate clockwise.

The problem with this approach is that the robot never terminates on its own. Since the robot runs forever, the simulation would also run forever unless we detect repetition.

A naive brute-force implementation might attempt to stop after some arbitrary number of moves, but that is not reliable because different rooms may require very different numbers of steps before entering a cycle.

Therefore, pure brute force without cycle detection is not practical.

Key Insight

The critical observation is that the robot's future behavior depends entirely on its current state:

  • current row
  • current column
  • current direction

If the robot ever reaches the exact same (row, column, direction) again, the future sequence of moves will repeat forever.

This means we only need to simulate until we revisit a previously seen state.

Since there are:

  • m * n possible positions
  • 4 possible directions

there are at most 4 * m * n unique states.

Once all reachable states are exhausted, a cycle must occur.

This transforms the infinite simulation into a finite simulation problem.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Infinite O(m × n) Cannot reliably terminate
Optimal O(m × n) O(m × n) Uses state cycle detection

Algorithm Walkthrough

Step 1: Define directions

The robot rotates clockwise, so we store the four directions in order:

  • Right
  • Down
  • Left
  • Up

We can represent them as:

directions = [(0,1), (1,0), (0,-1), (-1,0)]

The direction index determines where the robot faces.

Step 2: Track visited states

We create a set called visited_states.

Each state contains:

  • row
  • column
  • direction

For example:

(row, col, direction)

This is necessary because visiting the same cell with a different direction is not the same situation. The robot may behave differently depending on orientation.

Step 3: Track cleaned cells

We also maintain a set called cleaned.

Every time the robot visits an empty cell, we add it to this set.

At the end, the answer is simply:

len(cleaned)

Step 4: Simulate movement

At each iteration:

  1. Check whether the current state has already been seen.
  2. If yes, stop simulation because the robot has entered a cycle.
  3. Otherwise:
  • add state to visited_states
  • add current cell to cleaned

Then compute the next position.

Step 5: Handle movement or turning

If the next position:

  • is outside bounds, or
  • contains an obstacle,

then rotate clockwise:

direction = (direction + 1) % 4

Otherwise, move into the next cell.

Step 6: Return result

Once a repeated state appears, no new cells can ever be cleaned.

Return:

len(cleaned)

Why it works

The algorithm works because the robot is deterministic. Given the same position and direction, it will always make the same future decisions.

Therefore, once a state repeats, the entire future execution repeats as well. No unseen cells can ever be reached after that point.

Since there are finitely many possible states, the simulation must eventually terminate.

Python Solution

from typing import List, Set, Tuple

class Solution:
    def numberOfCleanRooms(self, room: List[List[int]]) -> int:
        rows = len(room)
        cols = len(room[0])

        # Right, Down, Left, Up
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        row = 0
        col = 0
        direction = 0

        visited_states: Set[Tuple[int, int, int]] = set()
        cleaned: Set[Tuple[int, int]] = set()

        while (row, col, direction) not in visited_states:
            visited_states.add((row, col, direction))
            cleaned.add((row, col))

            dr, dc = directions[direction]
            next_row = row + dr
            next_col = col + dc

            # Turn clockwise if blocked
            if (
                next_row < 0
                or next_row >= rows
                or next_col < 0
                or next_col >= cols
                or room[next_row][next_col] == 1
            ):
                direction = (direction + 1) % 4
            else:
                row = next_row
                col = next_col

        return len(cleaned)

The implementation closely follows the simulation process described earlier.

First, we store the four directions in clockwise order. This allows rotation using simple modular arithmetic.

The variables row, col, and direction represent the robot's current state.

Two sets are maintained:

  • visited_states tracks (row, col, direction)
  • cleaned tracks unique cleaned cells

The loop continues until a repeated state appears.

Inside the loop:

  1. The current state is recorded.
  2. The current cell is marked as cleaned.
  3. The next position is computed based on direction.
  4. If movement is impossible, the robot rotates clockwise.
  5. Otherwise, the robot advances forward.

Finally, the size of the cleaned set is returned.

Go Solution

func numberOfCleanRooms(room [][]int) int {
	rows := len(room)
	cols := len(room[0])

	// Right, Down, Left, Up
	directions := [][]int{
		{0, 1},
		{1, 0},
		{0, -1},
		{-1, 0},
	}

	row, col, direction := 0, 0, 0

	visitedStates := make(map[[3]int]bool)
	cleaned := make(map[[2]int]bool)

	for !visitedStates[[3]int{row, col, direction}] {
		visitedStates[[3]int{row, col, direction}] = true
		cleaned[[2]int{row, col}] = true

		dr := directions[direction][0]
		dc := directions[direction][1]

		nextRow := row + dr
		nextCol := col + dc

		if nextRow < 0 ||
			nextRow >= rows ||
			nextCol < 0 ||
			nextCol >= cols ||
			room[nextRow][nextCol] == 1 {

			direction = (direction + 1) % 4
		} else {
			row = nextRow
			col = nextCol
		}
	}

	return len(cleaned)
}

The Go implementation follows the same logic as the Python solution.

The main difference is that Go does not have built-in tuple types, so fixed-size arrays are used as map keys:

  • [3]int for robot states
  • [2]int for cleaned cells

Go maps naturally support these fixed-size arrays as hashable keys, making them a clean substitute for Python tuples.

No special overflow handling is needed because all indices remain within grid bounds.

Worked Examples

Example 1

Input:

room = [
  [0,0,0],
  [1,1,0],
  [0,0,0]
]

Initial state:

  • Position: (0,0)
  • Direction: Right
Step Position Direction Action Cleaned
1 (0,0) Right Move to (0,1) {(0,0)}
2 (0,1) Right Move to (0,2) {(0,0),(0,1)}
3 (0,2) Right Boundary hit, turn down {(0,0),(0,1),(0,2)}
4 (0,2) Down Move to (1,2) same
5 (1,2) Down Move to (2,2) add (1,2)
6 (2,2) Down Boundary hit, turn left add (2,2)
7 (2,2) Left Move to (2,1) same
8 (2,1) Left Move to (2,0) add (2,1)
9 (2,0) Left Boundary hit, turn up add (2,0)

Eventually the robot repeats a previous state.

Total cleaned cells:

7

Example 2

Input:

room = [
  [0,1,0],
  [1,0,0],
  [0,0,0]
]
Step Position Direction Action
1 (0,0) Right Obstacle, turn down
2 (0,0) Down Obstacle, turn left
3 (0,0) Left Boundary, turn up
4 (0,0) Up Boundary, turn right

Now the robot returns to:

(0,0,Right)

This state was already visited, so the simulation stops.

Only one cell was cleaned.

Answer:

1

Example 3

Input:

room = [
  [0,0,0],
  [0,0,0],
  [0,0,0]
]

The robot traverses the outer perimeter continuously.

The center cell (1,1) is never visited because the robot only turns when blocked.

Cleaned cells:

8

Complexity Analysis

Measure Complexity Explanation
Time O(m × n) Each state is processed at most once
Space O(m × n) Stores visited states and cleaned cells

There are at most 4 * m * n possible robot states because each cell can be visited facing four different directions.

The simulation terminates immediately after a repeated state is encountered, so every state is processed at most once.

The cleaned set and visited state set both scale linearly with the number of cells.

Test Cases

from typing import List

class Solution:
    def numberOfCleanRooms(self, room: List[List[int]]) -> int:
        rows = len(room)
        cols = len(room[0])

        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        row = 0
        col = 0
        direction = 0

        visited_states = set()
        cleaned = set()

        while (row, col, direction) not in visited_states:
            visited_states.add((row, col, direction))
            cleaned.add((row, col))

            dr, dc = directions[direction]
            next_row = row + dr
            next_col = col + dc

            if (
                next_row < 0
                or next_row >= rows
                or next_col < 0
                or next_col >= cols
                or room[next_row][next_col] == 1
            ):
                direction = (direction + 1) % 4
            else:
                row = next_row
                col = next_col

        return len(cleaned)

sol = Solution()

assert sol.numberOfCleanRooms([[0,0,0],[1,1,0],[0,0,0]]) == 7
# example 1

assert sol.numberOfCleanRooms([[0,1,0],[1,0,0],[0,0,0]]) == 1
# example 2

assert sol.numberOfCleanRooms([[0,0,0],[0,0,0],[0,0,0]]) == 8
# example 3

assert sol.numberOfCleanRooms([[0]]) == 1
# single cell room

assert sol.numberOfCleanRooms([[0,0,0,0]]) == 4
# single row

assert sol.numberOfCleanRooms([[0],[0],[0],[0]]) == 4
# single column

assert sol.numberOfCleanRooms([[0,1],[1,0]]) == 1
# trapped immediately

assert sol.numberOfCleanRooms([[0,0],[0,0]]) == 4
# small open square

assert sol.numberOfCleanRooms([[0,1,0],[0,1,0],[0,0,0]]) == 5
# obstacle corridor

assert sol.numberOfCleanRooms([[0,0,1],[1,0,1],[0,0,0]]) >= 1
# irregular obstacle pattern

Test Summary

Test Why
Example 1 Standard turning behavior
Example 2 Immediate trapped cycle
Example 3 Open grid perimeter traversal
Single cell Smallest possible input
Single row Horizontal boundary handling
Single column Vertical boundary handling
Trapped immediately Repeated state detection
Small open square Full traversal of small grid
Obstacle corridor Turning around obstacles
Irregular obstacles General robustness

Edge Cases

Single Cell Room

A 1 x 1 room is the smallest possible input. The robot starts at (0,0) and cannot move in any direction because every move hits a boundary.

A buggy implementation might accidentally loop forever without detecting repeated directional states. Our implementation correctly stores (row, col, direction) states, so after cycling through all four directions, the repeated state is detected.

Revisiting the Same Cell with Different Directions

A very common mistake is tracking only visited positions instead of full states.

For example, the robot may revisit (2,3) while facing a different direction. The future movement from that configuration may be completely different.

Our implementation avoids this bug by storing:

(row, col, direction)

instead of just (row, col).

Completely Open Grid

In an empty grid, the robot does not necessarily visit every cell.

For example, in a 3 x 3 empty room, the robot only traverses the perimeter and never enters the center.

A naive assumption that every empty cell gets cleaned would be incorrect. Our simulation follows the exact movement rules, so only genuinely visited cells are counted.