Practice/LinkedIn/Leetcode 489. Robot Room Cleaner

Leetcode 489. Robot Room Cleaner

CodingMust

Problem

You are controlling an autonomous vacuum robot placed in an unknown room. The robot has a limited API and cannot see the entire room layout. Your task is to program the robot to clean every accessible cell in the room.

The room is represented as a grid where:

• 1 represents an open cell that can be cleaned
• 0 represents an obstacle or wall that blocks movement

The robot starts at an unknown position facing an unknown direction and can only perform these operations:

• move(): Attempt to move forward one cell in the current direction. Returns true if the move succeeds, false if blocked by an obstacle or wall.
• turnLeft(): Rotate 90 degrees counterclockwise without moving.
• turnRight(): Rotate 90 degrees clockwise without moving.
• clean(): Clean the current cell.

Important: The robot has no access to a map, coordinates, or directional information. You must track position and orientation yourself.

Requirements

1. Clean every reachable cell exactly once
2. Use only the provided robot API methods
3. Handle obstacles and walls gracefully
4. Track visited cells to avoid infinite loops
5. Return the robot to its starting position and orientation (optional optimization)

Constraints

• The room dimensions are unknown and can be up to 100 x 100
• The robot will always start on a valid open cell
• There may be multiple disconnected regions (clean only the reachable area)
• You cannot make assumptions about the room's shape
• Time complexity should be O(N) where N is the number of reachable cells
• Space complexity should be O(N) for tracking visited cells

Examples

Example 1:

` Room Layout: 1 1 1 1 1 1 1 1 1

Robot starts at center cell (1,1) facing North

Output: All 9 cells cleaned Explanation: The robot systematically explores and cleans each accessible cell using depth-first traversal. `

Example 2:

` Room Layout: 1 1 1 1 0 1 1 1 1

Robot starts at (0,0) facing East

Output: 8 cells cleaned (all except the obstacle) Explanation: The robot navigates around the obstacle at position (1,1) and cleans all reachable cells. `

Example 3:

` Room Layout: 1 1 0 0 1 0 0 1 1

Robot starts at (0,0) facing South

Output: 5 cells cleaned in L-shaped pattern Explanation: The robot follows the connected path through the L-shaped accessible area. `