Implement the gasStationCircuitStart method that returns the gas station index from which the full circuit can be completed.
The input contains two arrays: gas and cost. At each station, gas[i] is the fuel available and cost[i] is the fuel needed to travel to the next station.
Your task is to return the starting station index from where the full circular route can be completed. If no such start exists, return -1.
For example, with gas = [1,2,3,4,5] and cost = [3,4,5,1,2], starting from index 3 allows completing the circuit.
Example 1
[1,2,3,4,5][3,4,5,1,2]53Example 2
[2,3,4][3,4,3]3-1Example 3
[5][4]10First, the total gas must be at least the total cost. If not, completing the route is impossible.
Then scan the stations while tracking the current tank balance. If the tank becomes negative at station i, no station from the current start up to i can be a valid start. Reset the start to i + 1 and start counting tank balance again.
After the scan, the stored start index is the valid answer.
Pseudocode:
function gasStationCircuitStart(gas, cost, size):
total = 0
tank = 0
start = 0
for i from 0 to size - 1:
balance = gas[i] - cost[i]
total = total + balance
tank = tank + balance
if tank < 0:
start = i + 1
tank = 0
if total < 0:
return -1
return start