Abstract / Summary

A robot moves on a grid according to given instructions and obstacles and stops if it hits an obstacle or moves outside the grid.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 65% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method robotSim that simulates the movement of a robot on a two-dimensional grid. The robot receives a sequence of integer commands that dictate turning or moving forward, while a set of obstacle coordinates restricts its path. The method returns the maximum Euclidean distance squared from the origin that the robot attains during the simulation.

Key Steps

The algorithm begins by converting the list of obstacle coordinates into a hash set for constant-time membership checks. This transformation is performed with a set comprehension:

stop = set((x, y) for x, y in obstacles)

The robot’s position is tracked by two integer variables x and y, both initialized to zero. Directional movement is encoded using a list of delta vectors, where each entry corresponds to north, west, south, and east respectively:

deltas = [[0, +1], [-1, 0], [0, -1], [+1, 0]]

A variable direction holds the current orientation index into the deltas list, starting at zero (north). The variable result stores the best distance squared observed so far.

The core of the method iterates over each command in the commands list. For a command equal to -1, the robot turns left; for -2, it turns right; any non-negative integer represents forward movement. The left turn logic decrements the direction index and wraps around from 0 to 3:

if c == -1:
    direction -= 1
    if direction == -1:
        direction = 3

The right turn logic increments the direction index and wraps from 3 back to 0:

elif c == -2:
    direction += 1
    if direction == 4:
        direction = 0

When the command is a positive step count, the algorithm extracts the appropriate delta vector for the current orientation:

dx, dy = deltas[direction]

A nested loop then attempts to move the robot one unit at a time, checking for obstacles before each step. If the next cell is occupied, the inner loop breaks, halting further movement for that command:

for k in range(c):
    if (x + dx, y + dy) in stop:
        break
    x += dx
    y += dy

After each command, the distance squared from the origin is recomputed and the maximum is retained:

result = max(result, x*x + y*y)

Finally, the method returns the recorded maximum distance squared:

return result

Edge Cases Handled

The implementation explicitly distinguishes between turning commands and movement commands, ensuring that a turn does not inadvertently cause movement. The wrap-around logic for the direction index guarantees correct orientation after any number of consecutive left or right turns, even when the robot turns more than a full circle.

Obstacle detection is performed before each unit step, which correctly handles scenarios where an obstacle lies directly adjacent to the robot’s current position. In such a case, the robot stops immediately without moving into the blocked cell, preserving the current coordinates for subsequent commands.

The initial position at the origin is considered in the distance calculation, so a command list containing only turns results in a distance of zero, which the algorithm returns correctly.

Performance Optimizations

The conversion of the obstacle list into a hash set enables O(1) average-case checks for the presence of a coordinate, eliminating the need for linear scans during movement. This choice is crucial for maintaining efficiency when the obstacle list is large.

Direction handling uses a small fixed-size list of delta vectors, allowing direct indexing without conditional branching for each possible orientation. The explicit wrap-around checks for the direction index avoid the overhead of modulo operations, which can be more expensive in tight loops.

The distance update uses a single max call after each command rather than recomputing the maximum after every individual step, reducing the number of comparisons performed during long forward movements.

Imagine a tiny robot living on a giant grid of squares. This code gives the robot a list of instructions to follow. First, there is a special box called a set that keeps track of where all the obstacles are, like big piles of blocks the robot cannot walk through. The robot starts at the very center where the coordinates are zero. There is a list of directions stored in memory that helps the robot know which way to look, like north, west, south, or east. The robot keeps track of which way it is currently facing by using a number from zero to three.

When the instructions start, the robot looks at each command one by one. If the command asks the robot to turn left or right, it simply changes the direction number so it faces a new way. If the command is a number, that tells the robot how many steps to take forward. Before each step, the robot checks its digital map to see if there is an obstacle in front of it. If it sees a block, it stays exactly where it is and stops walking. If the path is clear, the robot moves one square at a time. After every move, the robot calculates how far it has traveled from the center and remembers the furthest spot it ever touched.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python		TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++	JS	Java	C#	Rust	Python	Go	TS
	LeetcodeHelp	C++		Java			Python
	Progiez	C++		Java			Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	halfrost							Go
	JoshCrozier		JS
	lkwq007						Python
	lzl124631x	C++
	ruoru					Rust
	suxrobGM				C#
	varunu28			Java
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
withaarzoo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality