Intuition

The problem simulates the movement of a robot on a 2D plane, and the goal is to determine the maximum Euclidean distance the robot reaches from the origin (0,0). The robot can either move in the current direction, turn left, or turn right. Additionally, there are obstacles that block the robot's path. My initial thought was to simulate the movement while keeping track of the obstacles in a set for quick lookup.

Approach

1. First, we store the obstacles as strings in a set to allow constant-time checks for blocked positions.
2. We then define the possible movement directions for the robot (up, right, down, and left) using a 2D array.
3. The robot's movement is simulated by processing each command sequentially:
   • Turning left or right updates the direction index.
   • Moving forward checks if the next step is blocked by an obstacle. If it isn't, the robot moves; otherwise, the command is skipped.
4. At each step, the squared distance from the origin is updated, and the maximum distance is tracked.
5. Finally, we return the maximum squared distance achieved.

Complexity

• Time complexity:
  The time complexity is $O(n + m)$ where n is the number of commands and m is the number of obstacles. This is because we process each command in $O(1)$ time and check obstacles using a set, which provides average $O(1)$ lookup time.

• Space complexity:
  The space complexity is $O(m)$ where m is the number of obstacles, as we store all obstacles in a set.

Code

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

        int[][] directions = {
            { 0, 1 }, 
            { 1, 0 }, 
            { 0, -1 },
            { -1, 0 } 
        };

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

        for (int command : commands) {
            if (command == -2) {  // turn left
                direction = (direction + 3) % 4;
            } else if (command == -1) {  // turn right
                direction = (direction + 1) % 4;
            } else {
                int dx = directions[direction][0];
                int dy = directions[direction][1];
                for (int i = 0; i < command; i++) {
                    int nx = x + dx;
                    int ny = y + dy;
                    if (!obstaclesLookup.contains(nx + "," + ny)) {
                        x = nx;
                        y = ny;
                        maxDistance = Math.max(maxDistance, x * x + y * y);
                    } else {
                        break;
                    }
                }
            }
        }
        return maxDistance;
    }
}