LeetCode 489: Robot Room Cleaner Solution

Master LeetCode problem 489 (Robot Room Cleaner), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

489. Robot Room Cleaner

Hard

Backtracking Interactive

Problem Explanation

Explanation

To solve the "Robot Room Cleaner" problem, we can use backtracking along with a set to keep track of visited cells. We can define the robot's movements (up, down, left, right) and recursively explore all possible directions while cleaning the cells.

Algorithmic Idea:

Define the movements of the robot (up, down, left, right) and a helper function to move the robot in each direction.
Use backtracking to explore all possible directions while cleaning cells and marking visited cells.
Recursively move the robot in all directions while ensuring it does not move to a visited or obstacle cell.

Time Complexity:

The time complexity of this algorithm is O(4^n), where n is the number of cells to be cleaned.

Space Complexity:

The space complexity of this algorithm is O(n), where n is the number of cells to be cleaned.

Solution Code

class Solution {
    public void cleanRoom(Robot robot) {
        Set<String> visited = new HashSet<>();
        backtrack(robot, visited, 0, 0, 0);
    }
    
    private void backtrack(Robot robot, Set<String> visited, int x, int y, int direction) {
        String key = x + ":" + y;
        if (visited.contains(key)) return;
        
        robot.clean();
        visited.add(key);
        
        for (int i = 0; i < 4; i++) {
            if (robot.move()) {
                int newX = x, newY = y;
                switch (direction) {
                    case 0: newY--; break;
                    case 90: newX++; break;
                    case 180: newY++; break;
                    case 270: newX--; break;
                }
                backtrack(robot, visited, newX, newY, direction);
                robot.turnRight();
                robot.turnRight();
                robot.move();
                robot.turnRight();
                robot.turnRight();
            }
            robot.turnRight();
            direction += 90;
            direction %= 360;
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 489 (Robot Room Cleaner)?

This page provides optimized solutions for LeetCode problem 489 (Robot Room Cleaner) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 489 (Robot Room Cleaner)?

The time complexity for LeetCode 489 (Robot Room Cleaner) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 489 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 489 in Java, C++, or Python.

Back to LeetCode Solutions