874. Walking Robot Simulation

874

MediumMatrix and SimulationDirection vectors + hash set of obstaclesGrid walk simulation with heading state

Walking Robot Simulation

A robot starts at (0,0) on an infinite grid facing north. It processes a command list: -2 turns it left 90 degrees, -1 turns it right 90 degrees, and any value k from 1 to 9 moves it forward k unit-cells one at a time. If the next cell in its path is an obstacle, it stays put and ignores the remaining forward steps of that command. Return the maximum squared Euclidean distance (x*x + y*y) from the origin the robot ever reaches.

Open official problem prompt ↗

In plain English

Faithfully replay a robot's turn/move script on a grid with blocking obstacles and report the farthest squared distance from origin it ever attains.

Picture it like this

Like a Roomba following a taped-in program: it pivots in place on turn commands and rolls forward on move commands, bumping to a stop when it hits a wall, while you note the farthest spot from its dock.

Example

Input: commands = [4,-1,3], obstacles = []
Output: 25
Why: The robot moves north to (0,4), turns right to face east, moves to (3,4); the farthest point is (3,4) with 3*3 + 4*4 = 25.

Constraints

1 <= commands.length <= 10^4commands[i] is -2, -1, or an integer in [1, 9]0 <= obstacles.length <= 10^4-3 * 10^4 <= obstacles[i][0], obstacles[i][1] <= 3 * 10^4The answer is guaranteed to be less than 2^31

Pattern lesson

See the pattern, then code

Grid walk simulation with heading state

↗

Matrix and Simulation

Rotations, boundary walks, direction changes, or careful in-place state updates.. Encode the four headings as unit direction vectors in clockwise order so a right turn is +1 (mod 4) and a left turn is -1 (mod 4). Store obstacles in a set for O(1) blocking checks, and record the maximum distance after every single unit step, not just at command boundaries.

New words, made simpleKnow these before the algorithm

Heading: The direction the robot currently faces, tracked as an index into a fixed list of unit vectors.
Squared Euclidean distance: x*x + y*y; used instead of the actual distance to avoid floating-point square roots.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

List scan for obstacles

Too slow: with up to 10^4 obstacles and 10^4 steps this is quadratic and times out.

For each forward unit step, scan the obstacle list to check the next cell.

Time O(C * K)Space O(1)

Best choiceObstacle set + step-by-step simulation

Linear in commands plus obstacles; the intended solution.

Hash all obstacles once, then walk one cell at a time checking membership in O(1).

Time O(C + K)Space O(K)

The rule we keep true

Invariant

After each processed command, (x, y) holds the robot's true position, d holds its true heading, and best holds the maximum x*x+y*y over every cell the robot has occupied so far.

Why this is correct

Reasoning

Because forward motion is simulated one cell at a time and blocked exactly when the immediate next cell is an obstacle, the position always matches the robot's real trajectory. Tracking best after every unit step guarantees no intermediate maximum is missed even if the robot later moves back toward the origin.

The algorithm in three movesSay these aloud before coding

1Keep heading index d into a clockwise list of direction vectors [N,E,S,W]

face N, move 4 -> (0,4), best=16

2On -2 do d=(d-1)%4, on -1 do d=(d+1)%4

cmd -1 -> face E

3On k, step forward one cell up to k times, stopping early if the next cell is in the obstacle set

move 3 -> (3,4), best=25

4After each successful step, update best = max(best, x*x + y*y)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

start(0,0)0

north->(0,4)1

east->(3,4)2

1 · Readmove forward 4, facing N

2 · AskAny obstacle ahead? none

3 · Update statex=0,y=0,d=0

4 · Resultstep to (0,1),(0,2),(0,3),(0,4); best=16

Key takeaway

Key positions along the robot's path; the final point (3,4) gives the maximum squared distance 25.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Clockwise direction table
Index 0=North, 1=East, 2=South, 3=West so a right turn is +1 and a left turn is -1 modulo 4.
2
Lines 4Hash the obstacles
Converting to a set of tuples turns each next-cell block test into O(1).
3
Lines 12-17Forward walk with early stop
Move one unit at a time; break on hitting an obstacle so remaining forward steps of this command are skipped, and update best after each real step.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

No obstacles: robot moves freely
Obstacle directly in front on step 1: robot does not move at all for that command
Only turn commands: robot never leaves origin, answer stays 0
Robot circles back near origin: best is still retained from the earlier far point

Common beginner mistakes

Checking obstacles only at the end of a k-move command instead of each unit cell, letting the robot jump over a blocker
Computing max distance only at command boundaries and missing an intermediate peak
Mixing up left (-2) and right (-1), or using a counter-clockwise direction table so turns go the wrong way
Using actual sqrt distance and returning a float instead of the integer squared distance

Check your understanding

Why store obstacles in a set instead of scanning the list each step?

PyPython 3 · solution.py

Optimal

1class Solution:2    def robotSim(self, commands: list[int], obstacles: list[list[int]]) -> int:3        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]4        obs = {(ox, oy) for ox, oy in obstacles}5        x = y = d = 06        best = 07        for cmd in commands:8            if cmd == -2:9                d = (d - 1) % 410            elif cmd == -1:11                d = (d + 1) % 412            else:13                dx, dy = dirs[d]14                for _ in range(cmd):15                    if (x + dx, y + dy) in obs:16                        break17                    x += dx18                    y += dy19                    best = max(best, x * x + y * y)20        return best

Time complexityO(C + K)Optimized

Space complexityO(K)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleBloomberg

Walking Robot Simulation

Walking Robot Simulation

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Matrix and Simulation