Interview Classic 150 Problem P134 Gas Station

---

Timeline

Timeline

2025-10-05

init

Greedy

---

Problem:

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 starting from i, after reaching some point j, you find there is not enough gas, then all points between i and j (for example, suppose k is a point between i and j; starting from k, you have less gas by the amount from i to k) (the fact that you can reach k from i means the gas amount when reaching k is >= 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 gas required before reaching i to go to the next station
    //   if (gas[i] - cost[i] >= 0) {
    //     start = i;
    //     break;
    //   }
    // }
    // if (start == -1) {
    //   return -1;
    // }

    while (start < n) {
      curr_gas = 0;
      i = 0;
      // Go around once
      for (i = 0; i < n; i++) {
        idx = (start + i) % n;
        curr_gas += gas[idx] - cost[idx];
        if (curr_gas < 0) {      // Route failed
          start = start + i + 1; // Directly skip the failed interval
          // Successfully go around once
          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 once, the gas amount is always ≥ 0.

1. First, similarly, if starting from i, after reaching some point j, you find there is not enough gas, then all points between i and j are even less likely to reach j+1, because if k is a point between i and j, starting from k, you have less gas by the amount from i to k.

2. Next, for the total gas of the entire loop, total_gas: if total_gas - total_cost < 0, it means the entire loop does not have enough gas, no matter where the starting point is, it cannot succeed → return -1. If total_gas - total_cost >= 0, there must exist a unique starting point that can succeed, and this is the start returned at the end of 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 traversing only once is sufficient.

Then why is it enough to just traverse 0~n-1 and be done?

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

By contradiction: suppose the algorithm finally returns start, and there is a point k between start and n-1. Because the result is unique, if start cannot complete a full circle but k can, then since start can reach k, start should also be able to complete a full circle, contradicting the premise that if a solution exists it is unique. Therefore, when total >= 0, it is sufficient to traverse once; if there exists a start that can reach n-1, that 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 gas difference
        int curr_gas = 0;    // Current interval gas 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 gas is negative, it is impossible to go from start to i+1.
            if (curr_gas < 0) {
                // Use the next station as a new starting point
                start = i + 1;
                curr_gas = 0;
            }
        }

        // If the total fuel is less than 0, it means there is no solution
        return (total_diff >= 0) ? start : -1;
    }
};