Walking Through the Robot Bounded Box: A Simulation Approach

Simulation problems are a staple in technical interviews. They test your ability to translate verbal rules into clean, state-driven code. The Robot Bounded Box (or Robot Simulation) problem is a perfect example of this, requiring us to manage directional states and collision logic efficiently.

The Problem at a Glance

We have a robot starting at (0, 0) facing North. We receive a list of commands:

• -2: Turn left 90 degrees.
• -1: Turn right 90 degrees.
• 1 to 9: Move forward $X$ units.

Crucially, there are obstacles. If the robot encounters one, it stays in its current position and moves on to the next command. Our goal is to find the maximum squared Euclidean distance the robot ever reaches from the origin.

---

The Simulation Logic

To solve this efficiently, we focus on three pillars:

1. The Directional Compass

Instead of using complex if-else chains for turning, we use a 2D array to represent the four cardinal directions and an integer direction index.

• Turning Right: (direction + 1) % 4
• Turning Left: (direction + 3) % 4 (Adding 3 is equivalent to subtracting 1 in modulo 4 math, avoiding negative results).

2. Fast Collision Checking

Checking every obstacle in a list for every single step would be $O(M \times N)$, which is too slow. By converting obstacles into a HashSet of Strings (e.g., "x$y"), we can check for a collision in $O(1)$ time.

3. Step-by-Step Movement

Since we cannot "jump" over obstacles, we move one unit at a time for each movement command, checking the HashSet at every step.

---

Java Implementation

class Solution {
    // 0: North, 1: East, 2: South, 3: West
    private static final int [][] DIRECTION = new int [][]{
        {0, 1}, {1, 0}, {0, -1}, {-1, 0}
    };

    public int robotSim(int[] commands, int[][] obstacles) {
        if (commands == null || commands.length == 0) return 0;

        // Pre-process obstacles for O(1) lookup
        Set<String> obstacleSet = new HashSet<>();
        for (int[] obs : obstacles) {
            obstacleSet.add(obs[0] + "$" + obs[1]);
        }

        int x = 0, y = 0, direction = 0, maxDistSq = 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 {
                // Move step-by-step
                for (int i = 0; i < command; i++) {
                    int nextX = x + DIRECTION[direction][0];
                    int nextY = y + DIRECTION[direction][1];

                    if (!obstacleSet.contains(nextX + "$" + nextY)) {
                        x = nextX;
                        y = nextY;
                        maxDistSq = Math.max(maxDistSq, x * x + y * y);
                    } else {
                        break; // Hit an obstacle, stop moving
                    }
                }
            }
        }
        return maxDistSq;
    }
}

Complexity Analysis

Time Complexity (TC): O(N + M * K)

O(N): We iterate through the obstacles array once to populate our HashSet.
O(M*K): We process each of the M commands. For movement commands, we iterate up to K times (where K is the max steps, 9). Since K is a small constant, the simulation scales linearly with the number of commands.

Space Complexity (SC): O(N)

We store N obstacles in a HashSet using Long objects. This is much more memory-efficient than creating String objects for every coordinate and scales only with the number of obstacles.