Number of Spaces Cleaning Robot Cleaned - Solution & Explanation

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.