Gas Station
Problem Statement
There are n gas stations arranged in a circle. At station i, you can add gas[i] units of fuel, and it costs cost[i] units of fuel to travel from station i to station i + 1. You start with an empty tank. Return the starting station index if you can travel around the circuit once, otherwise return -1. If a valid answer exists, the problem guarantees it is unique.
Input
Two integer arrays gas and cost of equal length, describing fuel gained at each station and fuel needed for the next road segment.
Output
An integer: the unique valid starting index, or -1 if completing the circuit is impossible.
Constraints
- •
gas.length == cost.length - •
1 <= gas.length <= 10^5 - •
0 <= gas[i], cost[i] <= 10^4
Examples
Example 1
gas = [1,2,3,4,5], cost = [3,4,5,1,2]
3Example 2
gas = [2,3,4], cost = [3,4,3]
-1Learning Objectives
- Separate global feasibility from choosing the starting index.
- Use a running tank deficit to discard impossible starts in one scan.
- Explain why every station inside a failed segment can be skipped.
- Handle circular traversal without duplicating the array.
Intuition
Greedy Insight: if total gas is at least total cost, the problem guarantee means a unique valid start exists. While scanning left to right, keep a running tank for the current candidate start. If tank becomes negative at station i, then the current start cannot reach i + 1. Even better, no station between the candidate start and i can be valid either, so reset the candidate start to i + 1.
The reason is that every station inside that failed segment was reached with a nonnegative tank from the old candidate. Starting later would remove some earlier fuel that helped you reach it, so it cannot make the failed segment easier. The only possible next candidate is after the failure.
Common mistakes
- ×Trying every start and simulating the whole circle, which is O(n^2).
- ×Resetting the start when the global total is negative instead of when the current tank drops negative.
- ×Returning the candidate start without first checking total feasibility.
- ×Duplicating the circular route even though one linear scan of net gains is enough.
Algorithm Explanation
Greedy strategy
Track totalBalance over all stations and tank from the current candidate start. When tank becomes negative at index i, discard every start from the current candidate through i and set the candidate to i + 1.
Why it works
A negative tank means the candidate start cannot pay for the route through station i. Any later station inside the same segment had less prefix fuel available than the original candidate, because the original candidate reached it with a nonnegative tank after collecting all earlier segment gains. Therefore those starts also fail before or at the same boundary.
Proof of correctness
Whenever the scan resets after station i, suppose an optimal start s existed between the old candidate and i. The old candidate reached s with a nonnegative tank; removing that nonnegative prefix and starting at s cannot increase the fuel available for the remaining suffix from s through i. Since the old candidate has negative tank after i, start s must also fail by that point. This contradiction proves every skipped start is impossible. The scan therefore never discards a valid start. If totalBalance < 0, the entire circuit lacks enough fuel, so no start exists. If totalBalance >= 0, the remaining candidate is not discarded and, under the problem guarantee, is the unique valid start.
Algorithm
- Set start = 0, tank = 0, and totalBalance = 0.
- For each station, compute gain = gas[i] - cost[i].
- Add gain to both tank and totalBalance.
- If tank < 0, set start = i + 1 and reset tank = 0.
- After the scan, return start if totalBalance >= 0, otherwise return -1.
Solutions
Solution: Reset start after each failed segment
Use one pass to accumulate global feasibility and local candidate feasibility. A negative local tank proves the whole candidate segment is impossible, so the next candidate starts immediately after the failure.
Step-by-step
- Initialise start, tank, and totalBalance to 0.
- At each station, compute the net fuel change gas[index] - cost[index].
- Add that net change to the running candidate tank and to the global total balance.
- If the candidate tank becomes negative, move start to the next index and reset the tank to 0.
- At the end, return start only if the global total balance is nonnegative; otherwise return -1.
O(n)
O(1)
One scan processes every station once and stores only balances plus the candidate start.
Java implementation
Dry Run
Sample input
gas = [1,2,3,4,5], cost = [3,4,5,1,2]. Track local tank, global total, and the current start candidate.
| index | gas - cost | tank before | tank after reset check | total balance | start candidate |
|---|---|---|---|---|---|
| 0 | -2 | 0 | 0 | -2 | 1 |
| 1 | -2 | 0 | 0 | -4 | 2 |
| 2 | -2 | 0 | 0 | -6 | 3 |
| 3 | +3 | 0 | 3 | -3 | 3 |
| 4 | +3 | 3 | 6 | 0 | 3 |
The global total ends at 0, so a circuit is feasible. The only candidate not discarded is index 3, which is returned.
Interview Tips
Split the explanation into two claims: total gas must cover total cost, and a negative running tank discards an entire segment of starts. That second claim is the greedy proof interviewers care about. Avoid saying the largest gas station is best; the route depends on cumulative net gain, not local gas alone.
Likely follow-ups
- How would you return all valid starts if uniqueness were not guaranteed?
- What if the car starts with some initial fuel already in the tank?
- How would the answer change if the tank had a maximum capacity?
- Can you express the solution using the minimum prefix sum of net gains?
Similar Problems
Key Takeaways
- Global total balance decides whether any circuit is possible.
- A negative local tank proves the current candidate segment cannot contain the answer.
- Resetting after failure is safe because later starts in the failed segment have no extra fuel advantage.
- A circular route can often be solved with one linear scan over net changes.