Learning Outcome
After this lesson, you should be able to prove why a failed fuel segment cannot contain a valid start.
Problem Statement
Given gas and cost arrays, return the start index that lets you complete the circuit, or -1 if impossible.
| Input | Output | Why |
|---|---|---|
gas = [1,2,3,4,5], cost = [3,4,5,1,2] | 3 | Starting at index 3 gives enough fuel to complete the full loop. |
Brute Force Approach
Try every station as a start and simulate the full circuit. This costs O(n^2).
Optimized Approach
Track total fuel and a local tank. If the local tank becomes negative at i, no start from the current candidate through i can work, so reset start to i + 1.
Exact Pseudocode
total = 0
tank = 0
start = 0
for i from 0 to n - 1:
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0:
start = i + 1
tank = 0
if total < 0:
return -1
return startReference Code
class Solution:
def canCompleteCircuit(self, gas, cost):
total = 0
tank = 0
start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0:
start = i + 1
tank = 0
return -1 if total < 0 else startSample Dry Run
| Step | State | Result |
|---|---|---|
| Indexes 0 to 2 | tank becomes negative repeatedly | start moves forward |
| Index 3 | diff = 3 | start = 3, tank positive |
| Index 4 | tank remains positive | candidate survives |
| Total check | total fuel is non-negative | return 3 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | The arrays are scanned once. |
| Space | O(1) | Only total, tank, and start are stored. |
Edge Cases
- If total gas is less than total cost, return -1.
- The answer is unique in the standard version when one exists.
- Reset start only after local tank becomes negative.
Interview Checklist
- Track total feasibility separately from local tank.
- Reset candidate start to i + 1 on local failure.
- Return -1 when total is negative.
FAQs
Why can we skip starts before i + 1?
If the tank from the candidate start to i is negative, any start inside that segment has even less helpful prefix fuel.
Why still need total?
A local candidate can survive, but the whole circuit is impossible if total fuel is negative.
What is the core pattern?
Greedy reset after a failed segment.