There are n gas stations along a circular route. You are given two arrays: gas[i] is the fuel available at station i, and cost[i] is the fuel needed to travel from station i to the next station. Starting with an empty tank, find the starting station index from which you can complete the full circuit. If no solution exists, return -1. It is guaranteed that if a solution exists, it is unique.
For example, given gas = [1,2,3,4,5] and cost = [3,4,5,1,2], the answer is 3 (start at station 3).
Explain your approach and state the time and space complexity.
How to approach it
- Hint 1
If the total gas is less than the total cost, no solution exists. Otherwise, a solution is guaranteed.
- Hint 2
Track the current tank as you go. If the tank drops below zero at some station, that starting point and all stations before it cannot be the answer.
- Hint 3
Reset the starting station to the next station whenever the tank goes negative. The last reset point is the answer.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.