Number of Spaces Cleaning Robot Cleaned - Practice Coding Problems

Number of Spaces Cleaning Robot Cleaned - Problem

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.

Input & Output

Example 1 — Simple 3x3 Room

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

› Output: 7

💡 Note: Robot starts at (0,0) and moves right to (0,1), (0,2), then hits boundary and turns down to (1,2), then hits obstacle at (1,1) and continues cleaning path until cycle. Cleans 7 unique positions.

Example 2 — Single Row

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

› Output: 1

💡 Note: Robot starts at (0,0), tries to move right but hits obstacle at (0,1), turns down but hits boundary, continues turning until back to original state. Only position (0,0) is cleaned.

Example 3 — Open Rectangle

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

› Output: 4

💡 Note: Robot can move in a rectangular pattern: (0,0) → (0,1) → (1,1) → (1,0) → back to (0,0), cleaning all 4 positions.

Constraints

1 ≤ room.length, room[i].length ≤ 300
room[i][j] is either 0 or 1
room[0][0] == 0

Visualization

Tap to expand

Understanding the Visualization

Input Room

2D grid with obstacles (1) and empty spaces (0)

Robot Movement

Robot moves straight until hitting obstacle, then turns clockwise

Count Cleaned

Return number of unique positions visited before cycle

Key Takeaway

🎯 Key Insight: The robot will eventually enter a cycle when it returns to a previously visited state (position + direction)

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is that the robot will eventually return to a previous state (same position and direction), creating a cycle. We simulate the robot's movement, tracking all visited positions until cycle detection. The optimal approach uses bit manipulation for efficient state representation. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Simulation with State Tracking	O(m × n)	O(m × n)	Simulate robot movement until we detect a cycle
Efficient State Tracking	O(m × n)	O(m × n)	Use efficient data structures for state detection

Simulation with State Tracking — Algorithm Steps

Start at (0,0) facing right
Move forward until hitting obstacle or boundary
Turn 90° clockwise and repeat
Stop when we revisit a previous state
Count all unique positions visited

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Robot starts at (0,0) facing right

Move and Turn

Robot moves straight until hitting obstacle, then turns clockwise

Cycle Detection

When robot returns to a previous state, count all visited positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STATES 10000

typedef struct {
    int r, c, dir;
} State;

int solution(int** room, int rows, int cols) {
    if (rows == 0 || cols == 0) return 0;
    
    // Directions: right, down, left, up
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    int r = 0, c = 0, direction = 0;
    State states[MAX_STATES];
    int stateCount = 0;
    int positions[1000][2]; // Store unique positions
    int posCount = 0;
    
    while (stateCount < MAX_STATES) {
        // Check if state already exists
        int cycleFound = 0;
        for (int i = 0; i < stateCount; i++) {
            if (states[i].r == r && states[i].c == c && states[i].dir == direction) {
                cycleFound = 1;
                break;
            }
        }
        if (cycleFound) break;
        
        // Add current state
        states[stateCount++] = (State){r, c, direction};
        
        // Check if position already recorded
        int posExists = 0;
        for (int i = 0; i < posCount; i++) {
            if (positions[i][0] == r && positions[i][1] == c) {
                posExists = 1;
                break;
            }
        }
        if (!posExists) {
            positions[posCount][0] = r;
            positions[posCount][1] = c;
            posCount++;
        }
        
        // Try to move
        int dr = directions[direction][0], dc = directions[direction][1];
        int nr = r + dr, nc = c + dc;
        
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && room[nr][nc] == 0) {
            r = nr;
            c = nc;
        } else {
            direction = (direction + 1) % 4;
        }
    }
    
    return posCount;
}

int main() {
    // Simple parser for small test cases
    int rows = 0, cols = 0;
    int room[100][100];
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse basic 2D array format like [[0,0,0],[0,1,0],[0,0,0]]
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            cols = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    room[rows][cols++] = *ptr - '0';
                }
                ptr++;
            }
            rows++;
        }
        ptr++;
    }
    
    // Convert to pointer array
    int* roomRows[100];
    for (int i = 0; i < rows; i++) {
        roomRows[i] = room[i];
    }
    
    int result = solution(roomRows, rows, cols);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

In worst case, robot visits all empty cells multiple times before cycle detection

✓ Linear Growth

Space Complexity

O(m × n)

Set to store visited states (position + direction combinations)

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation with State Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler