Gas Station

Medium · Greedy · about 20 minutes

Asked at Amazon, Google, Bloomberg.

There are n gas stations on a circular route. Station i provides gas[i] fuel, and driving from station i to the next costs cost[i]. Starting with an empty tank, return the index of the station from which you can complete the full circuit once, or -1 if impossible. The answer is unique if it exists.