Abstract / Summary

Find the least time needed to reach a specific cell from the top left in a grid with movement rules.

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 56% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Graph Theory
• Heap (Priority Queue)
• Matrix
• Shortest Path

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 implementation solves a shortest-arrival-time problem on a rectangular grid where each cell contains a timestamp that indicates the earliest moment the cell can be entered. The algorithm explores the grid using a priority queue (min-heap) keyed by the time at which a cell can be reached. It expands states in increasing order of arrival time, guaranteeing that the first time the bottom-right corner is popped from the heap corresponds to the minimum feasible travel time.

Core Logic

Initialization

The grid dimensions are captured, and a quick feasibility test is performed for the two possible first moves. If both neighboring cells require a timestamp larger than 1, the start is isolated and the function returns -1 immediately.

height = len(grid)
width  = len(grid[0])

if grid[0][1] > 1 and grid[1][0] > 1:
    return -1

A heap named todo is seeded with the starting position (0,0) at time 0. The deltas tuple encodes the four orthogonal directions in a compact form, allowing iteration without constructing separate coordinate pairs.

todo   = [(0, 0, 0)]               # (time, x, y)
deltas = (0, +1, 0, -1, 0)         # dx, dy pairs via zip

Main Exploration Loop

The algorithm repeatedly extracts the state with the smallest timestamp from the heap.

while todo:
    now, x, y = heappop(todo)

If the extracted cell is the target (width-1, height-1), the current time now is the answer and the function returns it.

if x == width - 1 and y == height - 1:
    return now

A visited-cell marker is implemented by setting the grid entry to a negative value. When a cell is popped that has already been marked, the loop skips further processing.

if grid[y][x] < 0:
    continue
grid[y][x] = -1

The travel to any neighbor consumes one time unit, so now is incremented before neighbor handling.

now += 1

Neighbor Evaluation

For each of the four orthogonal directions, the algorithm computes the neighbor coordinates nx, ny. Boundary checks ensure the neighbor lies inside the grid.

for dx, dy in zip(deltas, deltas[1:]):
    nx = x + dx
    ny = y + dy

    if 0 <= nx < width and 0 <= ny < height:
        ...

The earliest possible arrival time at the neighbor is the maximum of the current time now and the neighbor’s timestamp grid[ny][nx].

arrive = max(now, grid[ny][nx])

If the neighbor has already been visited (negative marker), it is ignored.

if arrive < 0:
    continue

When the neighbor’s timestamp exceeds the current time, the algorithm must wait. The waiting period is expressed as pingpong = arrive - now. Because the waiting can be simulated by moving back and forth between the current cell and the neighbor, the parity of the waiting steps matters: an odd number of extra steps changes the parity of the arrival time, while an even number does not. The code adjusts arrive by adding pingpong & 1, which adds one extra step only when the waiting length is odd. This eliminates the need to explicitly simulate the back-and-forth moves.

if arrive > now:
    pingpong = arrive - now
    arrive  += pingpong & 1

Finally, the neighbor state is pushed onto the heap with its computed arrival time.

heappush(todo, (arrive, nx, ny))

If the heap becomes empty without reaching the target, the function returns -1, indicating that no feasible path exists.

return -1

Edge Cases Handled

The early check for both initial neighbors being unavailable prevents unnecessary heap work when the start is trapped.

The visited-cell marking using a negative sentinel avoids revisiting cells that have already been processed with the optimal arrival time, ensuring that each cell contributes at most one expansion to the heap.

The parity adjustment (pingpong & 1) correctly handles situations where the required waiting time is large. By collapsing a sequence of back-and-forth moves into a single parity correction, the algorithm respects the rule that moving to a neighbor and immediately returning consumes two time units, preserving the correct parity of the total steps.

The boundary checks (0 <= nx < width and 0 <= ny < height) guarantee that out-of-bounds accesses are never attempted, even when the grid is a single row or column.

The final return -1 covers the case where the destination is unreachable due to timestamp constraints that block all possible routes.

Performance Optimizations

The use of a min-heap (todo) ensures that states are expanded in non-decreasing order of arrival time, which is the classic Dijkstra-style approach for weighted graphs with non-negative edge costs. This ordering eliminates the need for a separate distance array because the first time a cell is popped from the heap is guaranteed to be its optimal arrival time.

In-place marking of visited cells (grid[y][x] = -1) removes the overhead of maintaining an auxiliary boolean matrix, reducing memory pressure and improving cache locality.

The deltas tuple provides a compact representation of direction vectors, allowing the neighbor loop to be written without allocating temporary lists or tuples on each iteration.

The parity shortcut (arrive += pingpong & 1) replaces a potentially large number of explicit “ping-pong” moves with a constant-time arithmetic adjustment. This dramatically cuts down the number of heap pushes that would otherwise be generated by simulating each back-and-forth step, especially when the timestamp gap is large.

Overall, the algorithm runs with a priority-queue-driven expansion that processes each cell at most once, and the constant-time tricks for waiting and direction handling keep the per-cell overhead minimal.

Imagine a giant grid that looks like a maze made of colorful stepping stones. Each stone has a special number printed on it that tells you exactly when you are allowed to land there. You start at the very top left corner and want to reach the finish line at the bottom right.

You keep a list of the places you can go next, starting with the very first stone. You always look at your list to pick the stone that lets you arrive as quickly as possible. When you reach a new stone, you peek at the number written on it. If the number is bigger than the time you have right now, you have to wait for the clock to catch up.

There is a fun trick for when a path is blocked by a shy stone that is not ready for you. If a neighbor is not yet ready, you can jump back and forth between two stones like you are playing a game of ping-pong. By bouncing back and forth, you can make the time pass just enough so that the path becomes open. You keep exploring these stones by trying every direction until you finally land on the stone that marks the end of the maze. Every time you step on a stone, you make sure to mark it as visited so you do not go in circles, and you keep going until the finish line is reached.

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		Go	Python	TS
	Progiez	C++		Java			Python
github	charles-wangkai			Java
	everthis		JS
	fsq	C++
	Shamik07				Dart
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
Shamik07	Dart
wisdompeak	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