874. Walking Robot Simulation

Description

A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot can receive a sequence of these three possible types of commands:

• 2: Turn left 90 degrees.
• 1: Turn right 90 degrees.
• 1 <= k <= 9: Move forward k units, one unit at a time. Some of the grid squares are obstacles. The ith obstacle is at grid point obstacles[i] = (xi, yi). If the robot runs into an obstacle, then it will instead stay in its current location and move on to the next command.

Return the maximum Euclidean distance that the robot ever gets from the origin squared (i.e. if the distance is 5, return 25).

Intuition:

• The robot's movement can be represented as a series of steps in different directions.
• The maximum distance from the origin is the square of the Euclidean distance between the robot's final position and the origin.
• Obstacles can prevent the robot from moving in certain directions, affecting its final position.

Approach:

Initialize variables:

• x and y to track the robot's current position (initially 0, 0).
• direction to represent the robot's current direction (initially 0 for north, 1 for east, 2 for south, 3 for west).
• max_distance to store the maximum distance squared. Iterate through commands:

For each command cmd:

• If cmd is -2 (turn left), update direction to (direction - 1) % 4.
• If cmd is -1 (turn right), update direction to (direction + 1) % 4.
• If cmd is a positive integer (move forward): Calculate the new x and y coordinates based on the current direction and the movement distance.
• Check if the new position is an obstacle. If so, skip the movement.
• Update max_distance if the new distance squared is greater than the current maximum.
• Return max_distance after processing all commands.

Complexity

Time complexity:

O(N), where N is the number of commands.

Space complexity:

O(M), where M is the number of obstacles (if using a hash set to check for obstacles).

Code

C++

class Solution {
public:
    int robotSim(vector& commands, vector>& obstacles) {
        vector> dirs = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}}; // east, south, west, north
        unordered_set obstacleSet;

        for (const auto& obs : obstacles) {
            obstacleSet.insert(to_string(obs[0]) + "," + to_string(obs[1]));
        }

        int idx = 3, x = 0, y = 0, res = 0;

        for (int e : commands) {
            if (e == -2) {
                idx = (3 + idx) % 4;
            } else if (e == -1) {
                idx = (1 + idx) % 4;
            } else {
                int dx = dirs[idx][0], dy = dirs[idx][1];
                for (int dis = 0; dis < e; ++dis) {
                    int nx = x + dx, ny = y + dy;
                    string k = to_string(nx) + "," + to_string(ny);
                    if (obstacleSet.count(k)) break;
                    x = nx;
                    y = ny;
                    res = max(res, x * x + y * y);
                }
            }
        }

        return res;
    }
};

Python

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        dirs = [(1, 0), (0, -1), (-1, 0), (0, 1)]  # east, south, west, north
        obstacle_set = {tuple(obs) for obs in obstacles}
        
        idx, x, y, res = 3, 0, 0, 0
        
        for e in commands:
            if e == -2:
                idx = (3 + idx) % 4
            elif e == -1:
                idx = (1 + idx) % 4
            else:
                dx, dy = dirs[idx]
                for _ in range(e):
                    nx, ny = x + dx, y + dy
                    if (nx, ny) in obstacle_set:
                        break
                    x, y = nx, ny
                    res = max(res, x * x + y * y)
        
        return res

Java

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int[][] dirs = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}}; // east, south, west, north
        Set obstacleSet = new HashSet<>();

        for (int[] obs : obstacles) {
            obstacleSet.add(obs[0] + "," + obs[1]);
        }

        int idx = 3, x = 0, y = 0, res = 0;

        for (int e : commands) {
            if (e == -2) {
                idx = (3 + idx) % 4;
            } else if (e == -1) {
                idx = (1 + idx) % 4;
            } else {
                int dx = dirs[idx][0], dy = dirs[idx][1];
                for (int dis = 0; dis < e; ++dis) {
                    int nx = x + dx, ny = y + dy;
                    String k = nx + "," + ny;
                    if (obstacleSet.contains(k)) break;
                    x = nx;
                    y = ny;
                    res = Math.max(res, x * x + y * y);
                }
            }
        }

        return res;
    }
}

JavaScript

/**
 * @param {number[]} commands
 * @param {number[][]} obstacles
 * @return {number}
 */
const robotSim = function (commands, obstacles) {

    const dirs = [[1, 0], [0, -1], [-1, 0], [0, 1]] // east, south, west, north
    const set = new Set()

    obstacles.forEach(([x, y]) => set.add(`${x},${y}`))
    let idx = 3, x = 0, y = 0, res = 0

    for (let e of commands) {

        if (e === -2) idx = (3 + idx) % 4
        else if (e === -1) idx = (1 + idx) % 4
        else {

            const [dx, dy] = dirs[idx]
            let dis = 0

            while (dis < e) {
                const nx = x + dx, ny = y + dy
                const k = `${nx},${ny}`
                if (set.has(k)) break
                x = nx
                y = ny
                dis++
                res = Math.max(res, x * x + y * y)
            }
        }
    }

    return res
};