Gas Station

The key idea

Two facts collapse the search. First, a full loop is possible only when total gas is at least total cost. Second, if the running tank ever drops below zero while driving from station start, then no station between start and the current one can be the answer either, so the only candidate left is the next station. One left-to-right pass finds it.

Problem

There are n gas stations arranged in a circle. The amount of gas at the i-th station is gas[i].

You have a car with an unlimited gas tank. It costs cost[i] of gas to travel from the i-th station to the next (i + 1)-th station. You begin the journey with an empty tank at one of the gas stations.

Given the two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If a solution exists, it is guaranteed to be unique.

Constraints

n == gas.length == cost.length
1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4
The answer is guaranteed to be unique if it exists.

Examples

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

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

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →