Gas Station
Part of Practice: Reach & Reset
There are n gas stations arranged in a circle. At station i you can add gas[i] units of fuel, and driving from station i to the next station costs cost[i] units. You start with an empty tank at a station of your choice. Return the index of the unique station from which you can drive all the way around the circle once, or -1 if no such station exists. The problem guarantees that if an answer exists, it is unique.
Constraints that matter: up to 100,000 stations, so trying every starting station and simulating a full lap (O(n²)) is too slow.
Examples
- Input:
- gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
- Output:
- 3
Start at station 3 with 4 units. Tank after each leg: 4-1+5=8 arriving at 4... in short, the tank never drops below zero on the full lap, which fails from any earlier start.
- Input:
- gas = [2, 3, 4], cost = [3, 4, 3]
- Output:
- -1
Total gas (9) is less than total cost (10), so no starting point can finish a lap.
- Input:
- gas = [5], cost = [4]
- Output:
- 0
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.