143. Gas Station
Start with an empty tank, collect fuel at the current station, and spend fuel to reach the next station in cyclic order. Find a station from which a full circuit can be completed without fuel becoming negative.
The tank has unlimited capacity, but you cannot borrow fuel before collecting it. Follow the contract's tie rule when several starting stations work.
Example 1
Input
gas=[1,2,3,4,5], cost=[3,4,5,1,2]
Output
3
Explanation: Starting at three yields nonnegative tank after each edge and returns to three.
Example 2
Input
gas=[2,3,4], cost=[3,4,3]
Output
-1
Explanation: Total available fuel is smaller than total cost.
Example 3
Input
gas=[0,0], cost=[0,0]
Output
0
Explanation: Both starts work; the strict-negative reset leaves zero as the selected start.
Constraints
0 <= gas.length == cost.length <= 1050 <= gas[i], cost[i] <= 231 - 1- Return any feasible starting index, or -1 when none exists.
Hints
Hint 1
What condition must total fuel satisfy regardless of the starting station?
Hint 2
If start first fails at i, what balance would a later start inside that segment have at i?
Hint 3
Reset only the local candidate tank, then use total conservation to justify the final wrap.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Repeated elimination followed by a successful wrap
[1,2,3,4,5]
[3,4,5,1,2]
3