We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Spaces Cleaning Robot Cleaned

Number: 2203

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given a 2D binary matrix where 0 represents an empty space and 1 represents an object, a cleaning robot starts at the top-left corner (which is always empty) facing right. The robot moves in a straight line until it either reaches the boundary or hits an object; at that point, it turns 90 degrees clockwise and continues. Each unique space that the robot visits (including its starting cell) is considered cleaned. The task is to determine how many unique spaces will be cleaned if the robot continues its movement indefinitely.

Key Insights

  • The robot moves in one of four directions: right, down, left, up.
  • The robot only changes direction when it is blocked by either a wall or an object.
  • It is essential to track the robot’s state (position and orientation) to detect cycles and prevent infinite simulation.
  • A state is defined by the cell coordinates and the current direction.
  • Use a set to record cleaned cells (for counting unique spaces) and another set for robot states (to detect cycles).

Space and Time Complexity

Time Complexity: O(m * n * 4) in the worst case, considering every possible unique combination of position and direction is visited once. Space Complexity: O(m * n * 4) due to the storage of visited states and cleaned cell information.

Solution

Simulate the robot’s movement using a loop. The state (position and direction) is tracked to detect cycles. Each time the robot moves to a new cell, add that cell to a set of cleaned cells. If the robot encounters an obstacle or boundary, it rotates 90 degrees clockwise and then attempts to move forward. The simulation stops when a previously seen state (cell plus direction) is encountered, ensuring we do not simulate indefinitely. This approach efficiently handles the robot's traversal across the grid.

Code Solutions

# Python solution for simulating the cleaning robot's movement.
# Define four possible directions: right, down, left, and up.
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def numberOfSpacesCleaned(room):
    m, n = len(room), len(room[0])
    cleaned = set()      # Set to store cleaned cells as (row, col)
    visited_states = set()  # Set to detect cycles: (row, col, direction index)
    
    row, col, d = 0, 0, 0    # Start at (0, 0) facing right (direction index 0)
    
    while (row, col, d) not in visited_states:
        visited_states.add((row, col, d))
        cleaned.add((row, col))
        
        dr, dc = directions[d]
        next_row, next_col = row + dr, col + dc
        
        # Check if next move is valid: in bounds and not an object.
        if 0 <= next_row < m and 0 <= next_col < n and room[next_row][next_col] == 0:
            row, col = next_row, next_col
        else:
            # If blocked, rotate 90 degrees clockwise.
            d = (d + 1) % 4
            
    return len(cleaned)

# Example usage:
room1 = [[0,0,0],[1,1,0],[0,0,0]]
print(numberOfSpacesCleaned(room1))  # Expected output: 7
← Back to All Questions