Abstract / Summary

A car drives east with limited fuel and must refuel at gas stations to reach a distant point using the fewest stops possible.

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 42% (400k+ submissions).

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 classic “minimum number of refueling stops” problem. It receives a destination distance (target), an initial amount of fuel (startFuel), and a list of gas stations where each station is represented by its distance from the start and the amount of fuel it can provide. The algorithm determines the smallest number of stops required to reach the destination, returning -1 when the journey is impossible.

The core idea is to greedily postpone refueling until it is necessary, while always selecting the previously passed station that offers the most fuel. This is achieved with a max-heap that stores the fuel amounts of all stations that have become reachable.

Key Steps

Sorting the stations

stations.sort()

Even though the problem statement does not guarantee that the input list is ordered, the algorithm explicitly sorts the stations by their distance from the start. This ensures that the subsequent while-loop can process stations in increasing order of reachability.

Initializing the heap and distance tracker

refuel   = []   # max-heap
distance = startFuel

refuel holds the fuel amounts of stations that are within the current reachable range. By storing the negative of each amount, the standard heapq module can be used as a max-heap. distance represents the farthest point that can be reached with the fuel accumulated so far.

Expanding the reachable set

while stations and stations[0][0] <= distance:
    more = stations.pop(0)[1]   # amount of fuel at this station
    heappush(refuel, -more)     # store as negative for max-heap behavior

The inner loop extracts every station whose distance does not exceed the current distance. Each station’s fuel amount is pushed onto the heap, making it available for a future refuel decision. By popping from the front of the list, the algorithm maintains a linear progression through the sorted stations.

Determining when refueling is required

if not refuel:
    return -1

If the heap is empty after attempting to collect all reachable stations, there is no previously passed station that can provide additional fuel. In this situation the vehicle cannot advance further, and the function returns -1 to indicate failure.

Selecting the best station to refuel

more      = -heappop(refuel)   # retrieve the largest fuel amount
distance += more              # extend the reachable distance
result   += 1

When additional fuel is needed, the algorithm extracts the maximum fuel amount from the heap (by negating the popped value). Adding this amount to distance simulates refueling at the most beneficial previously passed station, and the counter result is incremented to record the stop.

Loop termination

The outer loop repeats until distance meets or exceeds target. At that point the accumulated result value represents the minimal number of stops required to reach the destination, and it is returned.

return result

Edge Cases Handled

The code gracefully handles the situation where the initial fuel is already sufficient to reach the target; the outer loop condition while distance < target fails immediately, and the function returns 0.

When there are no stations (stations is empty), the inner loop never pushes any fuel onto the heap. If the initial fuel is insufficient, the if not refuel guard triggers and the function returns -1.

If multiple stations share the same distance, sorting places them together, and the inner loop will push all of their fuel amounts onto the heap before any refuel decision is made. The max-heap ensures that the algorithm always picks the station offering the greatest amount of fuel among those already passed.

When a station provides zero fuel, it is still pushed onto the heap as 0. The subsequent heappop will eventually retrieve a non-zero value if one exists; otherwise the algorithm will correctly identify that no useful fuel is available and return -1.

Performance Optimizations

The use of a max-heap (refuel) allows the algorithm to retrieve the largest available fuel amount in logarithmic time, which is more efficient than scanning the entire set of reachable stations at each refuel decision.

Sorting the stations once at the beginning eliminates the need for repeated ordering checks during the main loop.

By popping stations from the front of the sorted list (stations.pop(0)) only when they become reachable, the algorithm avoids revisiting stations that are already processed, ensuring each station is examined exactly once.

The combination of a single pass through the sorted stations and heap operations results in a solution that scales well with the number of stations, keeping the overall runtime low while maintaining correctness.

Imagine a car going on a big road trip to reach a destination far away. The car starts with a certain amount of fuel in the tank. Along the road, there are gas stations at different spots. Each station has a different amount of fuel available to fill up the tank. The goal is to reach that far destination while stopping as few times as possible.

To solve this, imagine a magic backpack that keeps track of all the gas stations reached so far. As the car drives, it looks at every station it can reach with the fuel it currently has. It picks up all the gas available at those reachable stations and puts the amount of fuel into the backpack. However, the special thing about this backpack is that it always makes the biggest pile of gas stay right on top.

Whenever the car runs out of fuel and has not reached the end yet, it reaches into the backpack and pulls out the biggest pile of gas available. Adding this fuel lets the car drive further. Every time fuel is pulled from the backpack, it counts as one stop. The car keeps doing this by picking up stations and grabbing the biggest piles of fuel until the car has enough gas to reach the final destination. The count of those stops is the answer.

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	Java	C++				Python			TS
	WalkCCC	Java	C++				Python
	leetcode.ca	Java	C++		Rust		Python		Go	TS
	LeetcodeHelp	Java	C++				Python
	Progiez	Java	C++				Python
github	black-shadows		C++
	charles-wangkai	Java
	everthis			JS
	fartem					Ruby
	FelixFan1122	Java
	gouthampradhan	Java
	JoshCrozier			JS
	lkwq007						Python
	ruoru				Rust
	suxrobGM							C#
	varunu28	Java
	vthwang	Java
	wisdompeak		C++
	zfang399		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	Java
gouthampradhan	Java
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
vthwang	Java
wisdompeak	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