Gas Station

Problem: Gas Station

We pick a random gas station I and try start from that point. If we cannot travel longer at gas station J, it's apparent that none of the stations between I and J can be picked as start point, then we can assume start points again from J + 1. In this problem, we can try pick the first gas station at the very beginning. Besides, we also need to maintain a global gas amount to ensure there's a global solution, not a partial one.

Code in Python:

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        sum, total, res = 0, 0, -1
        for i in xrange(len(gas)):
            sum += gas[i] - cost[i]
            total += gas[i] - cost[i]
            if sum < 0: sum, res = 0, i
        return -1 if total < 0 else res + 1