Interview Classic 150 Questions P134 Gas Station

---

Timeline

timeline

2025-10-05

init

greedy

---

Title:

P134 Gas Station

https://leetcode.cn/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150

Non-greedy algorithm: Based on the fact that if from i to some point j you find insufficient fuel, then all points between i and j (for example, suppose a point k between i and j, starting from k, you lack the fuel amount from i to k) (starting from i you can reach k, meaning fuel at k >= 0) are even less likely to reach j+1

#include <vector>
using std::vector;

class Solution {
public:
  int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    int n = gas.size();
    // int start = -1;
    int start = 0;
    int curr_gas;
    int i, idx;
    // for (int i = 0; i < n; i++) {
    //   // Minimum fuel before reaching i to go to the next
    //   if (gas[i] - cost[i] >= 0) {
    //     start = i;
    //     break;
    //   }
    // }
    // if (start == -1) {
    //   return -1;
    // }

    while (start < n) {
      curr_gas = 0;
      i = 0;
      // go around
      for (i = 0; i < n; i++) {
        idx = (start + i) % n;
        curr_gas += gas[idx] - cost[idx];
        if (curr_gas < 0) {      // route fails
          start = start + i + 1; // directly skip the failed interval
          // successfully go around
          break;
        }
      }
      if (i == n)
        return start;
    }

    return -1;
  }
};

Standard greedy solution:
We need to find a starting point start such that starting from start and going around the loop, the fuel amount is always ≥ 0.

1. First, similarly, if after going from i to some point j we find that fuel is insufficient, then all points between i and j, because assuming a point k between i and j, starting from k, having less fuel from i to k makes it even more impossible to reach j+1;

2. Secondly, for the total fuel of the entire loop total_gas: if total_gas - total_cost < 0, it means the entire loop has insufficient fuel, no matter where the start is, it cannot succeed → return -1, if total_gas - total_cost >= 0, there must be a unique starting point that can succeed, which is the start returned by the greedy method.

3. Furthermore, when we traverse from 0 to n-1, we have already filtered out all impossible starting points. And the problem guarantees that “If a solution exists, it is guaranteed to be unique”. If the final total >= 0, it means starting from the last start is feasible. This shows that only one traversal is needed.

Then why does it end after just traversing 0~n-1?

To put it more vividly: when curr_gas < 0, we always reset the starting point to the next position after the “lowest point of the fuel curve”, so the final start is the first station after the global minimum; and total >= 0 means that starting after the lowest point, the fuel will never drop below 0 again, so it can complete a full loop.

By contradiction: assume the solution returns start, and there is a point k between start and n-1. Because the result is unique, if start cannot complete a loop but k can, since start can reach k, start should also be able to complete a loop, which contradicts the premise that if a solution exists it is unique. Therefore, it is only necessary to traverse, and if total>=0, the existence of a start that can reach n-1 is the required result.

#include <vector>
using std::vector;

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int total_diff = 0;       // Total fuel difference
        int curr_gas = 0;    // Current interval fuel difference
        int start = 0;       // Current starting point

        int diff;

        for (int i = 0; i < n; i++) {
            diff = gas[i] - cost[i];
            total_diff += diff;
            curr_gas += diff;

            // If the current interval's fuel amount is negative, it is impossible to go from start to i+1
            if (curr_gas < 0) {
                // The next station as the new starting point
                start = i + 1;
                curr_gas = 0;
            }
        }

        // Total fuel amount is less than 0, indicating no solution
        return (total_diff >= 0) ? start : -1;
    }
};