1. One-Liner
Gas Station tries each station as start in O(n) by tracking tank; if tank goes negative, discard all previous candidates and start fresh from the next index—works if total gas ≥ total cost.
2. The Problem It Solves
Circular road with gas[i] and cost[i] between stations. Find a starting index to complete one loop with tank never negative, or -1 if impossible.
3. The Core Idea
If cumulative balance from a to b fails, no station in [a,b] can be a valid start (you’d still hit the same deficit). So jump start to b+1. Total feasibility check: sum(gas) ≥ sum(cost).
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Total check | If Σ gas < Σ cost, return -1 |
| 2. Tank | From start, add gas[i]-cost[i] each step |
| 3. Reset | If tank < 0, set start = i+1, tank = 0 |
| 4. Answer | Final start after one pass |
5. Dry Run Example
gas=[1,2,3,4,5], cost=[3,4,5,1,2]. Total gas = cost = 15 → possible. Sweep finds unique valid start (classic example reasoning).
6. Key Properties
| Property | Value |
|---|---|
| Linear scan | O(n) |
| Uniqueness | At most one start if feasible |
7. Where It Is Used
| Domain | Use |
|---|---|
| Interviews | Canonical greedy proof |
| CP | Circular array tricks |
8. Interview Tips
Prove failure segment can’t contain answer; mention two-pass or modulo indexing variant.
9. Comparison with Other Approaches
| Approach | Time |
|---|---|
| Greedy sweep | O(n) |
| Try all starts | O(n²) |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
Implementation Example (PYTHON)
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost):
return -1
start = tank = 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1
tank = 0
return start