Problem

Mr X is traveling by car on an expressway and there are several gas stations along the way at distances 0 = d0 < d1 < d2 < ... < dn from the starting point. The car can travel a maximum distance D when the fuel tank is full. Mr X aims to minimize the number of stops needed to reach the destination or travel the distance. Write a greedy algorithm that returns the minimum number of stops required.

Examples

Example 1

1
2
3
4
5
6
7

Input: gas_stations = [0, 100, 200, 300, 400], D = 250  
Output: 2  
Explanation:
- Start at 0.
- Reach station at 200 and refill.
- Reach station at 400 and refill.
Total stops = 2.

Example 2

1
2
3
4
5
6
7
8

Input: gas_stations = [0, 150, 300, 450, 600], D = 200  
Output: 3  
Explanation:
- Start at 0.
- Reach station at 150 and refill.
- Reach station at 300 and refill.
- Reach station at 450 and refill.
Total stops = 3.

Solution

Method 1 - Greedy strategy

Intuition

The goal is to minimise the stops while ensuring the car does not run out of fuel. At each step, you select the furthest reachable station ahead but within the current fuel range (D). If no such station exists, travel is impossible. This greedy approach works because choosing the furthest station ensures fewer stops while optimally utilising the fuel.

Approach

  1. Initial Conditions: Start from d0 = 0 with a full fuel tank allowing maximum travel of D.
  2. Greedy Selection: At every step, choose the furthest station reachable within the current fuel range to maximise distance covered.
  3. Refuel Count: Keep track of the number of refueling stops.
  4. Iterate:
    • Check reachable stations within the current fuel range.
    • If no further station is reachable before the fuel runs out, return -1 (indicating travel impossible).
    • Otherwise, move to the selected station and update the fuel range.
  5. Stopping Condition: Stop once the destination or travel distance is reached.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int minStops(vector<int>& gasStations, int D) {
        int stops = 0, currentPos = 0, maxReach = D;
        int n = gasStations.size();

        for (int i = 0; i < n; i++) {
            if (gasStations[i] > maxReach) {
                // If current station is out of reach, refill at last reachable station
                stops++;
                maxReach = currentPos + D;
                if (gasStations[i] > maxReach)
                    return -1;
            }
            currentPos = gasStations[i];
        }

        return stops;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public class Solution {
    public int minStops(List<Integer> gasStations, int D) {
        int stops = 0, currentPos = 0, maxReach = D;

        for (int station : gasStations) {
            if (station > maxReach) {
                // Refill at the last reachable station
                stops++;
                maxReach = currentPos + D;
                if (station > maxReach) {
                    return -1; // Not possible to proceed
                }
            }
            currentPos = station;
        }

        return stops;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def minStops(self, gas_stations, D):
        stops = 0
        current_pos = 0
        max_reach = D

        for gas_station in gas_stations:
            if gas_station > max_reach:
                # Refill at the last reachable station
                stops += 1
                max_reach = current_pos + D
                if gas_station > max_reach:
                    return -1  # Impossible to proceed
            current_pos = gas_station

        return stops

Complexity

  • ⏰ Time complexity: O(n). Iterating over stations and considering reachable distances requires linear time.
  • 🧺 Space complexity: O(1). Only variables to store the distance, fuel, and refuel counter are needed.