Greedy — Gas Station
↗ LeetCode: Gas Station · Medium · pattern chapter →
Asked atAmazonGoogleMetaBloomberg
Circular route: at station i you gain gas[i], pay cost[i] to reach i+1. Return start index that completes the loop, or -1.
Example 1 — gas=[1,2,3,4,5], cost=[3,4,5,1,2] → 3Example 2 — gas=[2,3,4], cost=[3,4,3] → -1
Constraints — 1 ≤ n ≤ 10⁵. Brute tries every starting station in O(n²) = 10¹⁰ ops at n=10⁵ (TLE). One-pass greedy using "total tank ≥ 0 → answer exists; skip to i+1 whenever running tank goes negative" is O(n) = 10⁵ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Try each start with simulation
O(n²). TLE.
Approach 2 — Single pass total + local reset (canonical)
Insight.
- If
Σgas < Σcost, impossible. - Walk once: track running
tank. Whentank < 0ati, no start in[startCandidate..i]works → resetstartCandidate = i+1,tank = 0.
java
int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int d = gas[i] - cost[i];
total += d; tank += d;
if (tank < 0) { start = i + 1; tank = 0; }
}
return total < 0 ? -1 : start;
}Execution Trace
Step 1 / 2reset; start=3
Complexity — Time O(n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Simulate | O(n²) | O(1) | TLE |
| Total + reset | O(n) | O(1) | canonical |
When to use which
- Circular feasibility problem with cost/gain → total + reset.
- Multiple valid starts → all indices past all resets are valid.
- Two-direction travel → separate check for each.
AI Study CompanionBeta
Related problems
- Candy — two-sweep sibling
- Best Sightseeing Pair
Was this page helpful?
📚 Related problems