Intervals & Greedy · 086Medium
Gas Station
There are n gas stations in a circle. gas[i] is the fuel available at station i, and cost[i] the fuel needed to reach station i+1. Starting with an empty tank, return the index you must begin at to travel the circuit once, or -1 if it is impossible. If a solution exists it is unique.
Constraints
- n == gas.length == cost.length
- 1 <= n <= 10^5
- 0 <= gas[i], cost[i] <= 10^4
Examples
canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2]) -> 3 canCompleteCircuit([2, 3, 4], [3, 4, 3]) -> -1 canCompleteCircuit([5], [4]) -> 0 canCompleteCircuit([2], [2]) -> 0 // n = 1, exactly enough fuel canCompleteCircuit([1], [2]) -> -1 // n = 1, not enough fuel canCompleteCircuit([3,1,1], [1,2,2]) -> 0 // the tank never dips below 0
Edge cases
- If total gas < total cost, no start works — return -1.
- The tank starts empty and may never go negative mid-journey.
- The route wraps around the end of the array.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — simulate a full circuit from every possible starting station.
- Target
- O(n) time, O(1) space — one pass: if the running tank goes negative at i, no station up to i can be the start, so restart from i + 1.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/11-intervals-greedy/086-gas-station.js ./practice c 086