Skip to content
Onsite
8 / 19

Gas Stations

MediumP2Coding

There are n gas stations on a circular route. Station i has gas[i] units of fuel, and driving from station i to station i + 1 (wrapping around) costs cost[i] units. You start with an empty tank at one of the stations and add all of that station's fuel when you arrive there.

Return the index of the station from which you can complete the full circle clockwise, or -1 if it is impossible. If a solution exists, it is guaranteed to be unique.

Example 1

Input
gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output
3
Why
Start at station 3 with 4, reach station 4 with 4 - 1 + 5 = 8, and so on.

Example 2

Input
gas = [2,3,4], cost = [3,4,3]
Output
-1

Constraints

  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4
  • If an answer exists it is unique.

Hints

Run checks the 3 visible tests, Submit all 8.