All problems

Gas Station

Medium · greedy

A road forms a loop through n fuel stops numbered 0 to n - 1. At stop i you can collect gas[i] units of fuel. Driving from stop i to the next stop costs cost[i] units of fuel, and after stop n - 1 the road returns to stop 0.

Your car has a tank that can hold any amount of fuel, and it starts empty. You choose one stop to begin at. There you collect its fuel, then drive round the loop in the order of the stop numbers, collecting the fuel at every stop you reach. The trip works if you can drive all the way back to the stop you began at without the tank ever being short for a leg of the journey. Arriving with exactly zero fuel left is fine.

Return the index of the stop where you can begin and finish the loop. If several stops work, return the smallest index. If no stop works, return -1.

Examples

Example 1

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

Output: 3

Starting at stop 3, the tank holds 3, 6, 4, 2 and finally 0 after each of the five legs, never below zero. No earlier stop works.

Example 2

Input: gas = [2, 3, 4], cost = [3, 4, 3]

Output: -1

There are 9 units of fuel in total, but the loop costs 10, so no start can work.

Example 3

Input: gas = [3, 3], cost = [3, 3]

Output: 0

Both stops work, since the tank is exactly empty each time it arrives. The smaller index is returned.

Constraints