Gas Station / Oasis / Car Path

EasyPython

Problem

A Bloomberg Terminal field vehicle must travel through a circular sequence of service stations. At station i, it can collect fuel[i] units of fuel, then needs distance[i] units to reach station (i + 1) % n.

Implement can_complete_circuit(fuel, distance) to return an index from which the vehicle can visit every station exactly once and return to its starting station. Return -1 if no such starting station exists. Assume the vehicle starts with an empty tank and has unlimited tank capacity.

Formal Specification

fuel: a list of n nonnegative integers, where fuel[i] is fuel available at station i.
distance: a list of n nonnegative integers, where distance[i] is fuel required to travel from station i to the next station.
Return an integer index in [0, n - 1], or -1 when completing the circuit is impossible.
The input lists have equal length and contain at least one station.

Constraints

1 <= n <= 10^5
0 <= fuel[i], distance[i] <= 10^4
fuel and distance have equal length
Return any valid starting index if one exists

Function Signature

def can_complete_circuit(fuel, distance):

Formal Specification

fuel: a list of n nonnegative integers, where fuel[i] is fuel available at station i.
distance: a list of n nonnegative integers, where distance[i] is fuel required to travel from station i to the next station.
Return an integer index in [0, n - 1], or -1 when completing the circuit is impossible.
The input lists have equal length and contain at least one station.