Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Example

Given 4 gas stations with gas[i]=[1,1,3,1], and the cost[i]=[2,2,1,1]. The starting gas station’s index is 2.

Note

The solution is guaranteed to be unique.

Challenge

O(n) time and O(1) extra space

Solution

Time:O(n)
if sum(gas) >= sum(cost), there must be a solution
From left to right, diff += gas[i]-cost[i], if diff<0, update the start index. A[0,index] can definitly be reached.

(Gas-Station.py) download

class Solution:
    # @param gas, a list of integers
    # @param cost, a list of integers
    # @return an integer
    def canCompleteCircuit(self, gas, cost):
        # write your code here
        if gas == None or cost == None:
            return -1

        # if sum(gas) < sum(cost), then no solution
        sum_gas = 0
        for i in gas:
            sum_gas += i
        sum_cost = 0
        for i in cost:
            sum_cost += i

        if sum_cost > sum_gas:
            return -1

        # Otherwise, there is a solution
        remain_gas = 0
        start_index = 0

        for i in range(gas):
            diff = gas[i] - cost[i]
            if remain_gas >= 0:
                remain_gas += diff
            else:
                # [0,i] can be passed, need to update start_index
                start_index = i
                remain_gas = diff
        return start_index