Gas Station Circuit

Problem

Given gas available at each station and the cost to travel to the next station, return the index of the unique starting station that completes the circuit, or -1 if none exists.

If total gas is less than total cost the answer is -1; otherwise scan once, resetting the candidate start whenever the running tank goes negative. Ties cannot occur.

Hint

If the tank empties at i, no start between the previous start and i can work either.

Test cases

case 1

in: [[1,2,3,4,5],[3,4,5,1,2]]

expected: 3

case 2

in: [[2,3,4],[3,4,3]]

expected: -1

case 3

in: [[1],[1]]

expected: 0

case 4

in: [[1,1],[1,1]]

expected: 0

case 5

in: [[5,1,2,3,4],[4,4,1,5,1]]

expected: 4

Starter codePython

def can_complete_circuit(gas, cost):
    # Your code here
    pass

5 test cases · run your code against them in the editor