Gas Station
mediumGreedy+20 XPTime limit 2s
n petrol stations stand on a circular road. Station i gives gas[i] litres, and driving from station i to station i + 1 (the last one leads back to station 0) uses cost[i] litres. Your tank is unlimited but starts empty. From which station can you start and drive once around the circle? Print -1 if no station works. When an answer exists, it is unique.
Input:
- line 1:
n - line 2:
gas[0] … gas[n−1] - line 3:
cost[0] … cost[n−1]
Output: the starting station's index, or -1.
Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ gas[i], cost[i] ≤ 10⁴.
Think about it: if total gas < total cost, it's impossible. Otherwise, drive from station 0; whenever the tank goes negative at station i, no station from the current start up to i can work — restart from i + 1. One O(n) pass.
Sample input 1
5 1 2 3 4 5 3 4 5 1 2
Sample output 1
3
Sample input 2
3 2 3 4 3 4 3
Sample output 2
-1
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).