Two Approaches for Gas Station Problem

Today, we'll share a story about a greedy old driver, which is related to LeetCode problem #134, "Gas Station":

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.

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.

The problem should be easy to understand. At each station i, you can refuel gas[i] liters of gas, but you need to consume cost[i] liters of gas to leave station i. The question is, from which station can you start and return to the starting point after a full circle?

Talking about the brute-force solution, it's quite straightforward. You can use a for loop to iterate through all stations, assuming each as a starting point, and then nest another for loop to check if you can complete a circle and return to the starting point:

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.