Share some of my ideas.


  • 242
    D

    I have thought for a long time and got two ideas:

    • If car starts at A and can not reach B. Any station between A and B
      can not reach B.(B is the first station that A can not reach.)
    • If the total number of gas is bigger than the total number of cost. There must be a solution.
    • (Should I prove them?)

    Here is my solution based on those ideas:

    class Solution {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
            int start(0),total(0),tank(0);
            //if car fails at 'start', record the next station
            for(int i=0;i<gas.size();i++) if((tank=tank+gas[i]-cost[i])<0) {start=i+1;total+=tank;tank=0;}
            return (total+tank<0)? -1:start;
        }
    };

  • 45
    C

    I have the same idea as yours. My thought corresponding to your second point is:

    • Every time a fail happens, accumulate the amount of gas that is needed to overcome the fail. After looping through the stations, if the gas left is more than gas needed, then we have a solution, otherwise not.

    Below is the Python code:

    class Solution:
        # @param gas, a list of integers
        # @param cost, a list of integers
        # @return an integer
        def canCompleteCircuit(self, gas, cost):
            gas_left = gas_needed = start = 0
            for i, (g, c) in enumerate(zip(gas, cost)):
                gas_left += g - c
                if gas_left < 0:
                    gas_needed -= gas_left
                    start = i + 1
                    gas_left = 0
            return start if gas_left >= gas_needed else -1

  • 0
    T
    This post is deleted!

  • 12
    W

    Here is another way: The first part is similar. I guess the main difference here from the others is in the last part when sum<=0.

    • Keep track of the running sum of an increasing window from start to end.
    • If sum>0, can keep traveling further, add station at the end.
    • Otherwise, try starting at an earlier station, since starting inside the window doesn't help.

    Note that sum from the start to the end station does not include the value at the end index, but include the value at the start index.

    My java code:

    public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
          int start=gas.length, end=0, sum=0;
          do sum+= sum>0? gas[end]-cost[end++]: gas[--start]-cost[start]; while (start!=end);
          return sum>=0? start: -1;
        }
    }
    

    Or write the loop in a better, expanded way:

      do {
          if (sum>0) { 
              sum  = sum+gas[end]-cost[end];
              end++;
          } else {
              start--;
              sum = sum + gas[start]-cost[start];
          }
      } while (start!=end);
    

  • 0
    S
    This post is deleted!

  • 0
    J

    Very nice code.


  • 0
    A

    The method of reduction to absurdity can prove it.


  • 0
    H

    excellent code, clear and neat


  • 130
    J

    I have exactly the same idea, this is my java solution.

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sumGas = 0;
        int sumCost = 0;
        int start = 0;
        int tank = 0;
        for (int i = 0; i < gas.length; i++) {
            sumGas += gas[i];
            sumCost += cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        if (sumGas < sumCost) {
            return -1;
        } else {
            return start;
        }
    }
    

    The reason why I think this works:
    1, if sum of gas is more than sum of cost, then there must be a solution. And the question guaranteed that the solution is unique(The first one I found is the right one).
    2, The tank should never be negative, so restart whenever there is a negative number.


  • 2
    Z

    Can you provide a proof?


  • 5
    P
    class Solution {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
            // solution:
            // if the sum of gas is greater than the sum of cost, then there's a solution
            // the start station of the solution exists after the greatest net deficit(GND) station
            // 0-------k--n  given net[0-n] > 0,  station k is GND
            // (1) for any station i between k and n, net[k-i] > 0, cause if not, k would not be the GND
            // (2) for any station j between 0 and k, net[k-n-j] > 0,
            //     cause net[k-n] + net[0-k] > 0, net[0-j] > net[0-k] (k is GND)
            int net = 0, gnd = -1, min =0;
            for (int i = 0; i < gas.size(); ++i) {
                net += gas[i] - cost[i];
                if (net < min) {
                    min = net;
                    gnd = i;
                }
            }
            if (net >= 0)
                return gnd + 1;
            else
                return -1;
        }
    };
    

    Hope it can help you.


  • 39
    S

    Proof to the first point: say there is a point C between A and B -- that is A can reach C but cannot reach B. Since A cannot reach B, the gas collected between A and B is short of the cost. Starting from A, at the time when the car reaches C, it brings in gas >= 0, and the car still cannot reach B. Thus if the car just starts from C, it definitely cannot reach B.

    Proof for the second point:

    • If there is only one gas station, it’s true.
    • If there are two gas stations a and b, and gas(a) cannot afford cost(a), i.e., gas(a) < cost(a), then gas(b) must be greater than cost(b), i.e., gas(b) > cost(b), since gas(a) + gas(b) > cost(a) + cost(b); so there must be a way too.
    • If there are three gas stations a, b, and c, where gas(a) < cost(a), i.e., we cannot travel from a to b directly, then:
    • either if gas(b) < cost(b), i.e., we cannot travel from b to c directly, then cost(c) > cost(c), so we can start at c and travel to a; since gas(b) < cost(b), gas(c) + gas(a) must be greater than cost(c) + cost(a), so we can continue traveling from a to b. Key Point: this can be considered as there is one station at c’ with gas(c’) = gas(c) + gas(a) and the cost from c’ to b is cost(c’) = cost(c) + cost(a), and the problem reduces to a problem with two stations. This in turn becomes the problem with two stations above.
    • or if gas(b) >= cost(b), we can travel from b to c directly. Similar to the case above, this problem can reduce to a problem with two stations b’ and a, where gas(b’) = gas(b) + gas(c) and cost(b’) = cost(b) + cost(c). Since gas(a) < cost(a), gas(b’) must be greater than cost(b’), so it’s solved too.
    • For problems with more stations, we can reduce them in a similar way. In fact, as seen above for the example of three stations, the problem of two stations can also reduce to the initial problem with one station.

    More readable version: http://blog.shengwei.li/leetcode-gas-station/


  • 0
    H

    I doubt your proof about the second point. Would you please elaborate your idea, especially the 4th step of the proof?


  • 0
    L

    I see your prove, it's cool, thanks for your prove.


  • 0
    L

    Yes, cool solution, and easy to understand.


  • 0
    S

    Can you explain me why do you reset the start to i+1 when the tank is <0? Basically you are saying if you can't reach from i...k..j, you cant reach from any k to j either.

    Based on my understanding, when tank < 0 and assume the current index is j, you proved that from i you can reach j-1. Now you reset start to j+1. If from there you can reach the end, you only proved that you can reach from j+1 to the end. It seems you missed out the check from j-1 -> j.


  • 0
    L

    Based on this rule:
    If car starts at A and can not reach B. Any station between A and B can not reach B.(B is the first station that A can not reach.), so the next possible start station is B.


  • 0

    I haven't tried/tested your code but it seems that start can be equal to gas.length which exceeds the array boundaries. Right ? Shouldn't you wrap it ?


  • 0
    W

    Can someone explain why "start" is the final answer. Assume that "start" is updated at i = k, and i = j, which means we start from station 0 can reach station k, but not k + 1; we start from k + 1, can reach station j but not j + 1. So if "start" is the final answer, I can assume that I will reach station k. But how are you sure about reaching station k + 1? or even station j + 1? Thanks!


  • 2
    D

    Sorry, could not get it at the proof of the first point.
    I think it should be "Exist" rather than "Any".
    If a car starts at A and can not reach B. "Exist" station between A and B can not reach B.(B is the first station that A can not reach.)
    Because you could fail at A to C but be successful at C to B. Thus , it can still reach B. Could anyone correct me?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.