LeetCode 874: Walking Robot Simulation Solution

Master LeetCode problem 874 (Walking Robot Simulation), a medium 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.

874. Walking Robot Simulation

Medium

Array Hash Table Simulation

Problem Explanation

Explanation:

To solve this problem, we can simulate the robot's movements while keeping track of obstacles it encounters. We will maintain the current position and direction of the robot and update it based on the commands received. We will also check for obstacles at each step and adjust the position accordingly.

Algorithm:

Initialize variables: x and y for current position, direction for current facing direction (0 for north, 1 for east, 2 for south, 3 for west), maxDistance to track the maximum squared Euclidean distance.
Create a set obstacleSet to store obstacles for efficient lookup.
Define movements for each direction: dx for x-coordinate changes and dy for y-coordinate changes based on the current direction.
Iterate through the commands:
- For -1 (turn right), update the direction to the right (clockwise).
- For -2 (turn left), update the direction to the left (counter-clockwise).
- For other commands, move one unit at a time in the current direction, checking for obstacles.
- Update the maxDistance with the squared Euclidean distance from the origin.
Return the maxDistance after executing all commands.

Time Complexity: O(N) where N is the number of commands.

Space Complexity: O(M) where M is the number of obstacles.

Solution Code

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        Set<String> obstacleSet = new HashSet<>();
        for (int[] obstacle : obstacles) {
            obstacleSet.add(obstacle[0] + " " + obstacle[1]);
        }

        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        int x = 0, y = 0, direction = 0, maxDistance = 0;

        for (int command : commands) {
            if (command == -1) {
                direction = (direction + 1) % 4;
            } else if (command == -2) {
                direction = (direction + 3) % 4;
            } else {
                for (int i = 0; i < command; i++) {
                    int newX = x + dx[direction];
                    int newY = y + dy[direction];
                    if (obstacleSet.contains(newX + " " + newY)) {
                        break;
                    }
                    x = newX;
                    y = newY;
                    maxDistance = Math.max(maxDistance, x*x + y*y);
                }
            }
        }

        return maxDistance;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 874 (Walking Robot Simulation)?

This page provides optimized solutions for LeetCode problem 874 (Walking Robot Simulation) 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 874 (Walking Robot Simulation)?

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

Can I run code for LeetCode 874 on DevExCode?

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

Back to LeetCode Solutions