LeetCode 874: Walking Robot Simulation

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:

1. 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.
2. Create a set obstacleSet to store obstacles for efficient lookup.
3. Define movements for each direction: dx for x-coordinate changes and dy for y-coordinate changes based on the current direction.
4. 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.
5. 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.

:

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;
    }
}