Abstract / Summary

You must find the fewest jumps to move through obstacles in a 3D grid by moving sideways or forward.

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

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Greedy

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 solves the “minimum side jumps” problem for a frog that moves forward along a three-lane road while avoiding obstacles. The algorithm processes the obstacle list in a single forward pass, maintaining the cheapest known number of side jumps required to reach each lane at the current position. By constantly updating these three values, the method arrives at the minimal total side jumps needed to reach the end of the road.

Key Steps

The core of the solution is the jumps array, which stores the current best cost for each lane. The array is initialized with the values [1, 0, 1], reflecting that the frog starts in the middle lane (lane 2) with zero jumps, while reaching the outer lanes would require one side jump.

jumps = [1, 0, 1]   # cost to be in lane 1, 2, 3 at the start

The algorithm iterates over each obstacle entry o in the input list. For each position, the lane that contains an obstacle is marked as invalid by assigning a large sentinel value (invalid = 999_999). This effectively removes that lane from consideration for the current step.

if o > 0:
    jumps[o - 1] = invalid

After invalidating the blocked lane, the algorithm determines the cheapest lane among the three by taking the minimum of the jumps array. This value, stored in low, represents the best cost achievable without a side jump at the current position.

low = min(jumps)

The next phase updates every lane that is not blocked. For each such lane, the new cost is the smaller of two possibilities: staying in the same lane (keeping the existing cost) or performing a side jump from the cheapest lane (low + 1). The expression min(low + 1, jumps[i]) captures this decision.

for i in range(3):
    if i != o - 1:
        jumps[i] = min(low + 1, jumps[i])

When the loop finishes processing all obstacles, the minimal value in jumps corresponds to the optimal number of side jumps required to reach the end of the road.

return min(jumps)

Edge Cases Handled

The algorithm gracefully handles a scenario where the obstacle list contains zeros, indicating no obstacle at that position. In such cases the if o > 0 block is bypassed, leaving all lanes valid for the update step. This ensures that the frog can continue forward without being forced to jump.

When an obstacle appears in the lane where the frog currently has the lowest cost, the invalidation step forces the algorithm to consider side jumps from the other lanes. Because the invalidated lane receives the sentinel value, it will never be selected as low in the same iteration, guaranteeing that the frog never attempts to occupy a blocked lane.

If the obstacle list begins with an obstacle in the middle lane (lane 2), the initial jumps array already reflects a cost of 0 for that lane. The invalidation step replaces this entry with the sentinel, causing the algorithm to immediately consider a side jump to either outer lane. The subsequent low computation will then select the cheaper of the two outer lanes, correctly accounting for the forced initial jump.

The sentinel value 999_999 is sufficiently large to dominate any realistic number of side jumps, ensuring that an invalidated lane is never chosen as the optimal path while still fitting comfortably within Python’s integer range.

Performance Optimizations

The solution achieves optimal runtime by processing the obstacle list exactly once. The inner loop iterates over a fixed size of three lanes, making the per-iteration work constant. This eliminates any need for nested loops over the obstacle array, which would increase the computational burden.

Using a single integer array (jumps) to store the state for all lanes avoids the overhead of more complex data structures such as dictionaries or priority queues. The constant-size array enables fast index-based access and updates.

The sentinel value technique removes the need for additional conditional checks when computing the minimum lane cost. By overwriting a blocked lane with a large number, the min(jumps) call automatically ignores it, simplifying the logic and reducing branching.

Overall, the algorithm’s design leverages minimal memory (three integers plus a few scalars) and a tight loop structure, delivering high efficiency for large input sizes.

Imagine a frog is trying to swim across a river that has three lanes. There are some rocks blocking parts of the lanes. The frog wants to get to the other side using the fewest number of jumps possible.

The code starts by keeping track of the frog in the middle lane. Because the frog is already in the middle, it takes zero jumps to be there, but it would take one jump to move to the top or bottom lane.

As the frog swims forward along the river, it looks at each obstacle one by one. If a rock appears in a lane, the frog makes a note that this lane is blocked by setting a very high number, representing that the frog cannot be there.

After checking for obstacles, the frog decides which lane is the best to be in. It looks at the jumps it has already made and checks if moving to a different lane would be better. It keeps updating the number of jumps it takes to be in each of the three lanes as it moves forward. By the time the frog reaches the end of the river, it looks at all three lanes and picks the one that took the smallest number of jumps to reach.

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

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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++		Python	Java			TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
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