# Walking Robot Simulation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/walking-robot-simulation)
Canonical: https://scaleengineer.com/dsa/problems/walking-robot-simulation
**Data structures:** Array, Hash Table
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe), [Jane Street](https://scaleengineer.com/companies/jane-street), [Shopify](https://scaleengineer.com/companies/shopify)
---
## Problem
A robot on an infinite XY-plane starts at point `(0, 0)` facing north. The robot receives an array of integers `commands`, which represents a sequence of moves that it needs to execute. There are only three possible types of instructions the robot can receive:

* `-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, it will stay in its current location (on the block adjacent to the obstacle) and move onto the next command.

Return the **maximum squared Euclidean distance** that the robot reaches at any point in its path (i.e. if the distance is `5`, return `25`).

**Note:**

* There can be an obstacle at `(0, 0)`. If this happens, the robot will ignore the obstacle until it has moved off the origin. However, it will be unable to return to `(0, 0)` due to the obstacle.
* North means +Y direction.
* East means +X direction.
* South means -Y direction.
* West means -X direction.

**Example 1:**

**Input:** commands = \[4,-1,3\], obstacles = \[\]

**Output:** 25

**Explanation:** 

The robot starts at `(0, 0)`:

1. Move north 4 units to `(0, 4)`.
2. Turn right.
3. Move east 3 units to `(3, 4)`.

The furthest point the robot ever gets from the origin is `(3, 4)`, which squared is `32 + 42 = 25` units away.

**Example 2:**

**Input:** commands = \[4,-1,4,-2,4\], obstacles = \[\[2,4\]\]

**Output:** 65

**Explanation:**

The robot starts at `(0, 0)`:

1. Move north 4 units to `(0, 4)`.
2. Turn right.
3. Move east 1 unit and get blocked by the obstacle at `(2, 4)`, robot is at `(1, 4)`.
4. Turn left.
5. Move north 4 units to `(1, 8)`.

The furthest point the robot ever gets from the origin is `(1, 8)`, which squared is `12 + 82 = 65` units away.

**Example 3:**

**Input:** commands = \[6,-1,-1,6\], obstacles = \[\[0,0\]\]

**Output:** 36

**Explanation:**

The robot starts at `(0, 0)`:

1. Move north 6 units to `(0, 6)`.
2. Turn right.
3. Turn right.
4. Move south 5 units and get blocked by the obstacle at `(0,0)`, robot is at `(0, 1)`.

The furthest point the robot ever gets from the origin is `(0, 6)`, which squared is `62 = 36` units away.

**Constraints:**

* `1 <= commands.length <= 104`
* `commands[i]` is either `-2`, `-1`, or an integer in the range `[1, 9]`.
* `0 <= obstacles.length <= 104`
* `-3 * 104 <= xi, yi <= 3 * 104`
* The answer is guaranteed to be less than `231`.

# Approaches
## Brute-Force Simulation with Linear Obstacle Search
This approach involves a direct simulation of the robot's movement. We track the robot's state (position and direction) and update it for each command. The main drawback is how we check for obstacles: for every single unit of movement, we perform a linear scan through the entire `obstacles` array. This is simple to implement but highly inefficient.
**Time:** O(N * M), where N is the number of commands and M is the number of obstacles. For each command, the robot can move up to 9 steps. For each step, we iterate through all M obstacles. This leads to a very high time complexity that is not feasible for the given constraints. · **Space:** O(1), as we only use a constant amount of extra space for variables like `x`, `y`, `dir`, and `maxDistSq`.
**Pros:** Simple to conceptualize and implement.; Requires no additional data structures, leading to minimal space usage.
**Cons:** Extremely inefficient due to the nested loops for movement and obstacle checking.; Will likely result in a 'Time Limit Exceeded' (TLE) error for large inputs.
### Explanation
We simulate the robot's path command by command. The robot's state is defined by its `(x, y)` coordinates and its current direction.

*   **State Initialization**:
    *   Position `(x, y)` starts at `(0, 0)`.
    *   Direction `dir` starts at `0` (North). We can map directions to coordinate changes using arrays: `dx = {0, 1, 0, -1}` and `dy = {1, 0, -1, 0}` for North, East, South, and West respectively.
    *   `maxDistSq` is initialized to `0`.
*   **Command Processing**:
    *   We iterate through the `commands` array.
    *   For a turn command (`-1` or `-2`), we update the `dir` variable. A left turn (`-2`) corresponds to `dir = (dir + 3) % 4`, and a right turn (`-1`) is `dir = (dir + 1) % 4`.
    *   For a move command `k`, we loop `k` times to move one unit at a time.
    *   In each step of the move, we calculate the next potential coordinates `(nextX, nextY)`.
    *   We then iterate through the entire `obstacles` array to check if `(nextX, nextY)` is an obstacle.
    *   If an obstacle is found, the robot stops, and we break out of the move loop.
    *   If no obstacle is found, the robot moves to `(nextX, nextY)`.
    *   After each command, we update `maxDistSq` with the current squared distance `x*x + y*y` if it's larger than the current maximum.

```java
class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int x = 0, y = 0;
        int dir = 0; // 0:N, 1:E, 2:S, 3:W
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int maxDistSq = 0;

        for (int command : commands) {
            if (command == -2) { // Turn left
                dir = (dir + 3) % 4;
            } else if (command == -1) { // Turn right
                dir = (dir + 1) % 4;
            } else { // Move forward
                for (int i = 0; i < command; i++) {
                    int nextX = x + dx[dir];
                    int nextY = y + dy[dir];
                    
                    boolean isObstacle = false;
                    for (int[] obstacle : obstacles) {
                        if (obstacle[0] == nextX && obstacle[1] == nextY) {
                            isObstacle = true;
                            break;
                        }
                    }

                    if (isObstacle) {
                        break; // Stop at current position
                    }

                    x = nextX;
                    y = nextY;
                }
            }
            maxDistSq = Math.max(maxDistSq, x * x + y * y);
        }
        return maxDistSq;
    }
}
```
### Algorithm
- Initialize robot position `(x, y) = (0, 0)`, direction `dir = 0` (North), and `maxDistSq = 0`.
- Define direction vectors `dx = {0, 1, 0, -1}` and `dy = {1, 0, -1, 0}`.
- Loop through each `command` in the `commands` array.
- If the command is a turn (`-1` or `-2`), update `dir`.
- If the command is a move `k`:
    - Loop `k` times to simulate one step at a time.
    - Calculate the next position `(nextX, nextY)`.
    - Iterate through the entire `obstacles` array to check if `(nextX, nextY)` is an obstacle.
    - If it is an obstacle, break the inner loop.
    - Otherwise, update `x = nextX`, `y = nextY`.
- After each command finishes, update `maxDistSq = max(maxDistSq, x*x + y*y)`.
- Return `maxDistSq` after all commands are processed.

## Optimized Simulation with Hashed Obstacle Set
This approach significantly improves performance by optimizing the obstacle detection process. Before starting the simulation, we preprocess the `obstacles` array by storing all obstacle coordinates in a `HashSet`. This allows for near-constant time, O(1), lookups. The simulation logic remains the same, but the check for an obstacle at each step becomes much faster.
**Time:** O(N + M), where N is the number of commands and M is the number of obstacles. It takes O(M) to build the `HashSet` and O(N) to process all commands, since each step within a command takes O(1) on average for the obstacle check. · **Space:** O(M), where M is the number of obstacles. This space is used to store the obstacle coordinates in the `HashSet`.
**Pros:** Highly efficient and will pass the given constraints.; The logic is a clear and standard optimization for lookup-heavy problems.
**Cons:** Requires extra space proportional to the number of obstacles.
### Explanation
The core idea is to trade space for time. By using a `HashSet`, we can check for the existence of an obstacle in average O(1) time, which is a massive improvement over the O(M) linear scan.

*   **Preprocessing**:
    *   Create a `HashSet` to store obstacle coordinates. To store a 2D point `(x, y)` in the set, we can encode it into a single unique value. A simple and effective method is to convert it to a string like `"x,y"`.
    *   Iterate through the `obstacles` array and add the string representation of each obstacle to the `HashSet`.
*   **Simulation**:
    *   The simulation proceeds as in the brute-force approach, with state variables `x`, `y`, `dir`, and `maxDistSq`.
    *   When processing a move command `k`, we again loop `k` times.
    *   In each step, after calculating `(nextX, nextY)`, instead of a linear scan, we perform a single lookup in our `HashSet`: `obstacleSet.contains(nextX + "," + nextY)`.
    *   If the lookup returns `true`, we've hit an obstacle and break the move loop.
    *   Otherwise, we update the robot's position.
    *   The `maxDistSq` is updated after each command is fully executed.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int x = 0, y = 0;
        int dir = 0; // 0:N, 1:E, 2:S, 3:W
        // dx[i] and dy[i] represent the change in x and y for direction i
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int maxDistSq = 0;

        // Store obstacles in a Set for O(1) average time lookups.
        // We encode a 2D point (x, y) into a single string "x,y".
        Set<String> obstacleSet = new HashSet<>();
        for (int[] obstacle : obstacles) {
            obstacleSet.add(obstacle[0] + "," + obstacle[1]);
        }

        for (int command : commands) {
            if (command == -2) { // Turn left 90 degrees
                dir = (dir + 3) % 4;
            } else if (command == -1) { // Turn right 90 degrees
                dir = (dir + 1) % 4;
            } else { // Move forward k units
                for (int i = 0; i < command; i++) {
                    int nextX = x + dx[dir];
                    int nextY = y + dy[dir];
                    
                    // Check if the next position is an obstacle
                    if (obstacleSet.contains(nextX + "," + nextY)) {
                        break; // Stop moving for this command
                    }
                    
                    // Move to the next position
                    x = nextX;
                    y = nextY;
                }
            }
            // Update the maximum squared distance after each command
            maxDistSq = Math.max(maxDistSq, x * x + y * y);
        }
        return maxDistSq;
    }
}
```
### Algorithm
- Create a `HashSet<String>` to store obstacle coordinates.
- Iterate through the `obstacles` array, convert each `(x, y)` pair to a string `"x,y"`, and add it to the set. This is a one-time preprocessing step.
- Initialize robot position `(x, y) = (0, 0)`, direction `dir = 0` (North), and `maxDistSq = 0`.
- Define direction vectors `dx = {0, 1, 0, -1}` and `dy = {1, 0, -1, 0}`.
- Loop through each `command`.
- If the command is a turn, update `dir`.
- If the command is a move `k`:
    - Loop `k` times.
    - Calculate the next position `(nextX, nextY)`.
    - Check if `obstacleSet.contains(nextX + "," + nextY)`. This is an O(1) average time check.
    - If it is an obstacle, break the inner loop.
    - Otherwise, update the robot's position.
- After each command, update `maxDistSq = max(maxDistSq, x*x + y*y)`.
- Return `maxDistSq`.

# Solutions
### Java

```java
class Solution {
public
  int robotSim(int[] commands, int[][] obstacles) {
    int[] dirs = {0, 1, 0, -1, 0};
    Set<Integer> s = new HashSet<>(obstacles.length);
    for (var e : obstacles) {
      s.add(f(e[0], e[1]));
    }
    int ans = 0, k = 0;
    int x = 0, y = 0;
    for (int c : commands) {
      if (c == -2) {
        k = (k + 3) % 4;
      } else if (c == -1) {
        k = (k + 1) % 4;
      } else {
        while (c-- > 0) {
          int nx = x + dirs[k], ny = y + dirs[k + 1];
          if (s.contains(f(nx, ny))) {
            break;
          }
          x = nx;
          y = ny;
          ans = Math.max(ans, x * x + y * y);
        }
      }
    }
    return ans;
  }
private
  int f(int x, int y) { return x * 60010 + y; }
}

```

### CPP

```cpp
class Solution {
public:
  int robotSim(vector<int> &commands, vector<vector<int>> &obstacles) {
    int dirs[5] = {0, 1, 0, -1, 0};
    auto f = [](int x, int y) { return x * 60010 + y; };
    unordered_set<int> s;
    for (auto &e : obstacles) {
      s.insert(f(e[0], e[1]));
    }
    int ans = 0, k = 0;
    int x = 0, y = 0;
    for (int c : commands) {
      if (c == -2) {
        k = (k + 3) % 4;
      } else if (c == -1) {
        k = (k + 1) % 4;
      } else {
        while (c--) {
          int nx = x + dirs[k], ny = y + dirs[k + 1];
          if (s.count(f(nx, ny))) {
            break;
          }
          x = nx;
          y = ny;
          ans = max(ans, x * x + y * y);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int: dirs = (0, 1, 0, - 1, 0) s = {(x, y) for x, y in obstacles} ans = k = 0 x = y = 0 for c in commands: if c == - 2: k = (k + 3) % 4 elif c == - 1: k = (k + 1) % 4 else: for _ in range(c): nx, ny = x + dirs[k], y + dirs[k + 1] if (nx, ny) in s: break x, y = nx, ny ans = max(ans, x * x + y * y) return ans

```