My AC is O(1) space O(n) running time solution. Does anybody have posted this solution?


  • 118
    X

    I have got one solution to this problem. I am not sure whether somebody has already posted this solution.

    class Solution {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    
           int start = gas.size()-1;
           int end = 0;
           int sum = gas[start] - cost[start];
           while (start > end) {
              if (sum >= 0) {
                 sum += gas[end] - cost[end];
                 ++end;
              }
              else {
                 --start;
                 sum += gas[start] - cost[start];
              }
           }
           return sum >= 0 ? start : -1;
        }
    };

  • 0
    M

    pretty good solution! and it's easy to understand.


  • 0
    W

    Can someone explain why the running time in worst case is not O(n^2)? Thanks.


  • 0
    Z

    During every iteration of the while loop, either end increases by 1 or start decreases by 1, so the while loop has exactly N-1 iterations.


  • 0
    S

    How can this method list all the possible start index i ?


  • -14
    J
    This post is deleted!

  • 0

    this one is nicer than the most voted thread.


  • 1
    K

    Can you please explain the solution??


  • 4

    Take the begin (0) as end and end( gas.size()-1 ) as start is really brilliant !
    I have the similar idea but I must deal with edge cases when start gets at 0 or end gets at end(gas.size()-1).
    You avoid these edge cases with this trick!

    I am not the owner of this solution, here is some explanation according to the code.

    The main idea is that every time we go to the next station as far as possible (remained gas is bigger or equal to 0) until we can not (remained gas is less than 0).
    Then we must extend our start station to the "last station" ( the station before start station) to find a possible solution.
    Repeat these two steps until we have checked all stations(start == end).

    We can travel around the circuit only if the remained gas is bigger or equal to 0!


  • 0
    M

    @yanchao_hust Thanks for the explanation. But what's the point of end++ while sum >= 0 ?


  • 0
    H

    @mugua-stolaf It means when your remaining gas is greater than 0 you can try go further.


  • 4
    H

    My understanding:

    The basic idea is every time we start from a station, we go as far as possible by increasing end until remaining gas is less than 0. If 'end' finally hits start we know we can travel around from 'start'. If we haven't traveled around, we know we cannot start from this station. Then we check the station before our start station if we can start from this station. Repeat until we have checked all stations.

    Note there is a little trick that every time we try to find the next start station, we always to back to extend the distance from start to end so that we can check all stations on the circuit. Otherwise, if we move start forward to decrease the distance from start to end, we are likely to end up with only checking part of the circuit. Another trick is we start from the end of the array so as to avoid some corner cases.


  • -2
    H

    @yanchao_hust Are you from Wuhan?


  • -2
    T

    @hzhu007 what is wuhan ,,,haha


  • 0
    B

    A smart solution! You must have very clear comprehension about this question;)


  • 0
    T

    @wz366 It is obviously that the loop will just run gas.size()-1 times so the time complexity is O(n).


  • 0

    @mugua-stolaf Every time we go to the next station as far as possible (remained gas is bigger or equal to 0) until we can not (remained gas is less than 0). sum >= 0 means that we can go to the next station, so we extend the current end to the next one, that is the point of end++


  • 1
    Q

    I haven't seen your code before. But our code is extremely similar.


Log in to reply
 

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