Two Approaches for Gas Station Problem

labuladongOriginalAbout 2375 words

This article will resolve

LeetCode	Difficulty
134. Gas Station	🟠

Today we discuss a story of a greedy driver, related to LeetCode Problem 134: "Gas Station":

134. Gas Station | LeetCode | 🟠

There are n gas stations along a circular route, where the amount of gas at the i^th station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i^th station to its next (i + 1)^th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Constraints:

n == gas.length == cost.length
1 <= n <= 10⁵
0 <= gas[i], cost[i] <= 10⁴

The problem is not difficult to understand. At each station i, you can add gas[i] liters of fuel, but leaving station i requires cost[i] liters. The task is to determine from which station you can start to complete a circle and return.

For a brute-force solution, it's easy to think of using a for loop to iterate through all stations, assuming each as a starting point, and then nest another for loop to check if a complete circle back to the starting point is possible:

int n = gas.length;
for (int start = 0; start < n; start++) {
    for (int step = 0; step < n; step++) {
        int i = (start + step) % n;
        tank += gas[i];
        tank -= cost[i];
        // determine if the gas in the tank is exhausted
    }
}

It is evident that the time complexity is $O(N^2)$ . Such a straightforward and crude approach is certainly not optimal. Let us analyze whether there is room for optimization.

Does the brute-force method involve redundant calculations? Can we abstract a "state," and are we calculating the same "state" multiple times?

In our previous article In-depth Explanation of Dynamic Programming, we mentioned that the changing variables are the "states." Observing the process of this brute-force enumeration, there are two changing variables: the "starting point" and the "current fuel in the tank." However, the combination of these two states surely has at least $O(N^2)$ possibilities, indicating no obvious space for optimization.

Therefore, this problem is definitely not about improving the efficiency of the brute-force method through simple pruning. Instead, we need to discover some deeper hidden patterns to reduce redundant calculations.

Below, we introduce two clever methods to solve this problem: the mathematical graphical method and the greedy method.

Two Approaches for Gas Station Problem

134. 加油站 https://leetcode.cn/problems/gas-station

134. Gas Station https://leetcode.com/problems/gas-station

Graphical Solution

Greedy Solution