LeetCode: 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.

Note:
The solution is guaranteed to be unique.

---

Since it is a circle, we can assume the start point is 0, when the gas is not enough to use, we can make the start point backwards one stop and see if current start point is available.

C++ Code:

/*
 * func: can_complete_circuit
 * goal: find the starting gas station that can make the truck travel the circuit
 * @param gas: gas vector
 * @param cost: cost vector
 * return: starting index
 */
int can_complete_circuit(vector<int> &gas, vector<int> &cost){
    int stop_num = gas.size();
    int start = 0;
    int end = stop_num-1;
    int current = 0;
    int remaining = 0;
    while(current <= end){
        remaining += gas[current] - cost[current];
        while(remaining < 0 && end != current){
            start = end;
            end = end-1;
            remaining += gas[start] - cost[start];
        }
        ++current;
    }
    
    return remaining < 0 ? -1 : start;
}

Python Code:

# func: find the starting gas station that can make the truck travel the circuit
# @param gas: gas list
# @param cost: cost list
# @return: the start position
def can_complete_circuit(gas, cost):
    start = 0
    end = len(gas)-1
    current = 0
    remaining = 0
    while current <= end:
        remaining += gas[current] - cost[current]
        while remaining < 0 and current != end:
            start = end
            end -= 1
            remaining += gas[start] - cost[start]
        current += 1

    if remaining < 0:
        return -1
    else:
        return start