874. Walking Robot Simulation

Array
Hash Table
Simulation

TIME

O(n + m) where n = total steps, m = obstacles

SPACE

O(m)

Intuition

Simulate the robot's movement step by step. Use direction vectors and a set for O(1) obstacle lookup. Track maximum squared distance after each step.

Solution

Direction Handling

Use direction vectors in order: North, East, South, West

directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
           =  North   East    South    West

Turn right: dir = (dir + 1) % 4
Turn left: dir = (dir + 3) % 4 (or (dir - 1 + 4) % 4)

Obstacle Set

Convert obstacles to a set of tuples for O(1) lookup:

obstacle_set = {(x, y) for x, y in obstacles}

Movement

For each move command k:

Move one step at a time (k times)
Check if next position is an obstacle
If blocked, stop moving for this command
Update max squared distance after each step

Why Step One at a Time?

We can't jump k units, obstacles might block partway through.

Complexity

Time: O(n + m) where n = total steps, m = obstacles
Space: O(m) for obstacle set

Edge Cases

Obstacle at origin (0, 0)
No obstacles
All turns, no movement
Blocked immediately

Code

from typing import List


class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        """
        874. Walking Robot Simulation
        Time: O(n + m) where n = total steps, m = obstacles
        Space: O(m)
        """
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        obstacle_set = {(x, y) for x, y in obstacles}

        x, y = 0, 0
        d = 0
        max_dist = 0

        for cmd in commands:
            if cmd == -2:
                d = (d + 3) % 4
            elif cmd == -1:
                d = (d + 1) % 4
            else:
                dx, dy = directions[d]
                for _ in range(cmd):
                    nx, ny = x + dx, y + dy
                    if (nx, ny) in obstacle_set:
                        break
                    x, y = nx, ny
                    max_dist = max(max_dist, x * x + y * y)

        return max_dist

import java.util.*;

/**
 * 874. Walking Robot Simulation
 * Time: O(n + m) where n = total steps, m = obstacles
 * Space: O(m)
 */
class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        Set<String> obstacleSet = new HashSet<>();
        for (int[] obs : obstacles) {
            obstacleSet.add(obs[0] + "," + obs[1]);
        }

        int x = 0, y = 0;
        int d = 0;
        int maxDist = 0;

        for (int cmd : commands) {
            if (cmd == -2) {
                d = (d + 3) % 4;
            } else if (cmd == -1) {
                d = (d + 1) % 4;
            } else {
                int dx = directions[d][0];
                int dy = directions[d][1];

                for (int i = 0; i < cmd; i++) {
                    int nx = x + dx;
                    int ny = y + dy;

                    if (obstacleSet.contains(nx + "," + ny)) {
                        break;
                    }

                    x = nx;
                    y = ny;
                    maxDist = Math.max(maxDist, x * x + y * y);
                }
            }
        }

        return maxDist;
    }
}