Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Minimum Number of Refueling Stops
Bookmark
Brute Force
DP
Greedy + Heap
Input
Example 1
Impossible
Already there
Two stations
Custom
target
=
100
,
startFuel
=
10
,
stations
=
[[10,60],[20,30],[30,30],[60,40]]
0
target 100
60
10
30
20
30
30
40
60
car
0
target 100
60
10
30
20
30
30
40
60
car
stops =
0
fuel =
10
/ best =
∞
0
target 100
60
10
30
20
30
30
40
60
car
fuel
10
<
target − pos
100
stops =
1
fuel =
60
/ best =
∞
0
target 100
60
10
30
20
30
30
40
60
car
stop at station 0 → fuel
60
, stops
1
stops =
1
fuel =
60
/ best =
∞
0
target 100
60
10
30
20
30
30
40
60
car
stops
1
<
best
∞
→ keep exploring
stops =
2
fuel =
80
/ best =
∞
0
target 100
60
10
30
20
30
30
40
60
car
stop at station 1 → fuel
80
, stops
2
stops =
1
fuel =
60
/ best =
2
0
target 100
60
10
30
20
30
30
40
60
car
station 2 is
20
away, fuel
60
→ within reach
stops =
2
fuel =
70
/ best =
2
0
target 100
60
10
30
20
30
30
40
60
car
fuel
70
≥
target − pos
70
stops =
1
fuel =
60
/ best =
2
0
target 100
60
10
30
20
30
30
40
60
car
station 3 is
50
away, fuel
60
→ within reach
stops =
2
fuel =
50
/ best =
2
0
target 100
60
10
30
20
30
30
40
60
car
target reached in
2
→ best =
2
stops =
0
fuel =
10
/ best =
2
0
target 100
60
10
30
20
30
30
40
60
Minimum stops = 2
algo
master
.
io
Step:
Start: Reach position 100 with the fewest refueling stops
0 / 21
Input
Example 1
Impossible
Already there
Two stations
Custom
target
=
100
,
startFuel
=
10
,
stations
=
[[10,60],[20,30],[30,30],[60,40]]
0 / 21
algo
master
.
io
Step:
Start: Reach position 100 with the fewest refueling stops
