Based on the question description, the direction should be clockwise.


  • 0
    C

    After checking the discussion here I found some guys are wondering whether we can travel from right to left, I checked based on the test cases on LeetCode OJ, we can only travel from left to right, as clockwise direction. The first function below is from right to left and can't pass the OJ like the case: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]. If we can travel from right to left, then 4 (the last station) should be the starting point, while the OJ said we should return 3, which is corresponding to the second function, from left to right. After checking the question description carefully, we can find that "it costs cost[i] of gas to travel from station i to its next station (i+1)", so it means we can only travel from smaller number station to bigger number station, and the last station is a special case, which will return to the first station, station 0. Actually I think for this kind of greedy questions or dynamic questions, if we didn't encounter them before or didn't practice intensively, it will be quite hard to devise a solution in a 45 minutes interview. So practice, practice, practice ...

    # can't pass OJ
    def canCompleteCircuit1(self, gas, cost):
        ret, s, cur = len(gas)-1, 0, 0
        for i in xrange(len(gas)-1, -1, -1):
            cur += (gas[i] - cost[i])
            s += (gas[i] - cost[i])
            if cur < 0:
                cur = 0
                ret = i - 1
        return -1 if s < 0 else ret
        
    # can pass OJ
    def canCompleteCircuit2(self, gas, cost):
        ret, s, cur = 0, 0, 0
        for i in xrange(len(gas)):
            cur += (gas[i] - cost[i])
            s += (gas[i] - cost[i])
            if cur < 0:
                cur = 0
                ret = i + 1
        return -1 if s < 0 else ret

Log in to reply
 

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