Skip to main content
Talentd

Number of Spaces Cleaning Robot Cleaned - Solution & Explanation

MediumPremiumFree on FleetCodeArrayMatrixSimulation6 min readAsked at: Microsoft, Geico
Practice this problem

Problem Statement

A room is represented by a 0-indexed 2D binary matrix room where a 0 represents an empty space and a 1 represents a space with an object. The top left corner of the room will be empty in all test cases.

A cleaning robot starts at the top left corner of the room and is facing right. The robot will continue heading straight until it reaches the edge of the room or it hits an object, after which it will turn 90 degrees clockwise and repeat this process. The starting space and all spaces that the robot visits are cleaned by it.

Return the number of clean spaces in the room if the robot runs indefinitely.

 

Example 1:

 

Input: room = [[0,0,0],[1,1,0],[0,0,0]]

Output: 7

Explanation:

  1. ​​​​​​​The robot cleans the spaces at (0, 0), (0, 1), and (0, 2).
  2. The robot is at the edge of the room, so it turns 90 degrees clockwise and now faces down.
  3. The robot cleans the spaces at (1, 2), and (2, 2).
  4. The robot is at the edge of the room, so it turns 90 degrees clockwise and now faces left.
  5. The robot cleans the spaces at (2, 1), and (2, 0).
  6. The robot has cleaned all 7 empty spaces, so return 7.

Example 2:

 

Input: room = [[0,1,0],[1,0,0],[0,0,0]]

Output: 1

Explanation:

  1. The robot cleans the space at (0, 0).
  2. The robot hits an object, so it turns 90 degrees clockwise and now faces down.
  3. The robot hits an object, so it turns 90 degrees clockwise and now faces left.
  4. The robot is at the edge of the room, so it turns 90 degrees clockwise and now faces up.
  5. The robot is at the edge of the room, so it turns 90 degrees clockwise and now faces right.
  6. The robot is back at its starting position.
  7. The robot has cleaned 1 space, so return 1.

Example 3:

Input: room = [[0,0,0],[0,0,0],[0,0,0]]

Output: 8​​​​​​​

 

 

Constraints:

  • m == room.length
  • n == room[r].length
  • 1 <= m, n <= 300
  • room[r][c] is either 0 or 1.
  • room[0][0] == 0

Approach Overview

Problem Overview: You are given a grid where 0 represents an empty space and 1 represents an obstacle. A robot starts at the top-left corner facing right and moves according to simple rules: move forward if the next cell is empty, otherwise rotate 90° clockwise. The robot stops once it repeats the same position and direction. The task is to count how many unique empty spaces the robot cleans.

Approach 1: Naive Simulation Without State Tracking (Potentially Unbounded)

This approach directly simulates the robot’s movement using the rules described. At each step, compute the next cell based on the current direction. If the cell is within bounds and not blocked, move forward and mark it as cleaned. Otherwise rotate the direction clockwise. The issue is that the robot can enter a movement cycle, causing an infinite loop if you do not track states. In practice you would need an artificial step limit such as m * n * 4. Time complexity is roughly O(m * n * 4) in the best controlled scenario, with O(m * n) space to track cleaned cells.

Approach 2: Simulation with Visited State Detection (O(m*n))

The correct approach treats the robot’s state as a combination of (row, col, direction). Even if the robot revisits the same cell, the behavior can differ depending on the direction it faces. Store every visited state in a set or boolean structure. During simulation, if the current state has already appeared, the robot has entered a loop and the process stops. Maintain another structure to track cleaned cells so that each empty cell contributes to the final count only once. The movement logic is simple: attempt to move forward using direction arrays; if blocked or out of bounds, rotate clockwise and stay in place.

This method guarantees termination because there are only m * n * 4 possible states. Each state is processed at most once, giving O(m * n) time complexity and O(m * n) space complexity. The implementation is straightforward using arrays and a loop, which is why the problem is commonly categorized under simulation and grid traversal problems.

The grid itself is naturally modeled as a matrix, and movement directions can be stored in a small array such as [(0,1),(1,0),(0,-1),(-1,0)]. Using these offsets simplifies turning logic and keeps the code concise. Most solutions rely only on basic array operations.

Recommended for interviews: Interviewers expect the state-tracking simulation. Starting with a plain simulation shows you understand the movement rules, but recognizing that (row, col, direction) defines the full state demonstrates stronger problem-solving. Detecting cycles using a visited-state set is the key insight that makes the algorithm reliable and efficient.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Simulation Without State TrackingO(m*n*4)O(m*n)Useful for understanding robot movement rules but unsafe without a loop guard
Simulation with Visited (row, col, direction) StateO(m*n)O(m*n)Recommended solution that safely detects cycles and guarantees termination

Video Solution

2061. Number of Spaces Cleaning Robot Cleaned - Week 3/5 Leetcode May Challenge • Programming Live with Larry • 658 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Number of Spaces Cleaning Robot Cleaned easy or hard?
The problem is rated Medium because the movement rules are simple but detecting cycles requires careful thinking. Recognizing that direction must be part of the state is the key step to avoid infinite loops.
Number of Spaces Cleaning Robot Cleaned Python/Java solution
The typical implementation uses a loop that simulates robot movement while storing visited (row, col, direction) states. Direction arrays handle movement and clockwise rotation. The same logic translates cleanly across Python, Java, C++, and Go with O(m*n) complexity.
How to solve Number of Spaces Cleaning Robot Cleaned in O(n)?
Use simulation with direction arrays and a visited-state set. Track the robot's position and direction, attempt to move forward, and rotate clockwise if blocked. Stop when the same (row, col, direction) state repeats. Since the number of states is bounded by m*n*4, the total runtime becomes O(m*n).
What is the best approach for Number of Spaces Cleaning Robot Cleaned?
The best approach is simulation with visited state tracking. Treat the robot's state as (row, column, direction) and store visited states in a set or boolean array. Once the same state appears again, the robot is in a loop and the simulation stops. This guarantees O(m*n) time because there are only m*n*4 possible states.
Is Number of Spaces Cleaning Robot Cleaned asked at Google/Amazon/Meta?
Grid simulation and robot movement problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations often test state tracking, cycle detection, and careful implementation of movement rules on a matrix.
What data structure is used in Number of Spaces Cleaning Robot Cleaned?
The solution mainly uses arrays for the grid and direction vectors, plus a set or boolean structure to track visited states. Each state stores row, column, and direction to detect loops during the simulation.
What is the time complexity of Number of Spaces Cleaning Robot Cleaned?
The optimal solution runs in O(m*n) time. Each unique state defined by (row, column, direction) can be processed only once, and there are at most m*n*4 states. The space complexity is also O(m*n) for tracking visited states and cleaned cells.

Ready to solve this problem?

Practice Number of Spaces Cleaning Robot Cleaned with our built-in code editor and test cases.

Practice on FleetCode
Previous

Robot Room Cleaner