Problem overview
There are n gas stations on a circular route. Station i has gas(i) units of gas, and driving from station i to the next one costs cost(i). After station n - 1 comes station 0 again. The tank is unlimited and starts empty. At each station you take all its gas, then drive on, and a stretch is possible only if the tank holds at least its cost.
The method canCompleteCircuit returns the station to start from so that you drive once around the circle and get back, or -1 if no start works. At most one station works.
For gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2] the answer is 3. Starting there you take 4, and the tank goes 4, then 4 - 1 + 5 = 8, 8 - 2 + 1 = 7, 7 - 3 + 2 = 6, 6 - 4 + 3 = 5, and the last stretch costs exactly the 5 that is left. For gas = [2, 3, 4] and cost = [3, 4, 3] the answer is -1: there are 9 units of gas in all and the trip costs 10.
Approach: skip every start that fails
Trying every start and simulating the whole circle costs O(n^2). The statement asks for O(n) time and O(1) extra space, which a greedy scan gives. It rests on two observations.
The total decides whether any start exists. Add up gas(i) - cost(i) over all stations. If the sum is negative, the trip costs more than all the gas there is, and no start can work. If it is not negative, a start exists, and the problem is to find it.
A failure rules out a whole stretch of starts. Drive once from station 0 to the last station, keeping a candidate start (first 0) and the tank. If the tank drops below 0 after the stretch that follows station i, the car could not have driven it. None of the stations from the candidate to i can be the start either. The car reached each of them with 0 or more gas, and starting at one of them means arriving there with an empty tank, which is never better, so the tank would still go negative at the same point. The next candidate is i + 1, with an empty tank.
The last candidate is the answer. The stretches skipped before it lose gas overall, but the total is not negative, so what the car has left at the end of the list covers them. Inside a skipped stretch the tank only goes negative at its very end, so with that gas the car gets through each stretch and back to the start.
The tank on the first example, with the candidate after each station:
i=0 tank=0 start=1
i=1 tank=0 start=2
i=2 tank=0 start=3
i=3 tank=3 start=3
i=4 tank=6 start=3
The tank is reset to 0 each time the candidate moves. From station 3 on, it never drops below 0, and the method returns 3.
Step by step
- Store the number of stations,
gas.length, in avalnamedn. - Declare
totalwithvar, set to 0. It adds up the gas taken minus the gas spent over all stations. It is avarbecause the loop changes it. - Loop over every station with
i <- 0 until n. - Add
gas(i) - cost(i)tototalwith+=: what stationigives minus what the stretch after it costs. - Return -1 early if
total < 0. No start can pay for the whole trip. Otherwise one exists. - Declare
startas avarset to 0, the station being tried. Station 0 is tried first. - Declare
tankas avarset to 0, the gas in the tank when driving fromstart. - Loop over the stations again with
i <- 0 until n. One drive from station 0 to the last one is enough. - Take the gas and drive the stretch: add
gas(i) - cost(i)totank. Afterwards,tankis the gas left on arriving at the next station. - Check for a dry tank with
tank < 0. Exactly 0 is fine: the car arrives empty and can still take the next station's gas. - Move
starttoi + 1, the station after the stretch where the tank ran dry. - Empty the tank by setting it to 0, since the trip now begins again at the new start.
- End with
startas the last expression.
The solution in Scala
class Solution {
def canCompleteCircuit(gas: Array[Int], cost: Array[Int]): Int = {
val n = gas.length
var total = 0
for (i <- 0 until n) {
total += gas(i) - cost(i)
}
if (total < 0) {
return -1
}
var start = 0
var tank = 0
for (i <- 0 until n) {
tank += gas(i) - cost(i)
if (tank < 0) {
start = i + 1
tank = 0
}
}
start
}
}
The Scala details worth a closer look:
valversusvar.nnever changes, so it is aval.total,startandtankchange inside loops, so they arevars. Scala rejects an assignment to aval.untilexcludes its end.0 until ngives the indices 0 ton - 1, which are exactly the valid indices of the arrays.0 to nwould run one index past the end.- Early
return. Thereturn -1sits inside anif, outside any closure, so it leaves the method directly. Everywhere else the method relies on the last expression,start, being the result. startstays a valid index. Whentotalis not negative, the final candidate is always less thann. If the tank were negative at the very last station, the sum of everything would be negative too, and the method would already have returned -1.Intis enough. It is 32 bits and wraps on overflow, but with up to 100000 stations and values up to 10000, each sum stays within 10^9, well inside its range.
Complexity
Time: O(n). The method makes two passes over the stations, each doing constant work per station.
Space: O(1). It keeps four integers and builds no extra array.
Edge cases and common mistakes
- One station.
gas = [5]andcost = [4]give 0: the station pays for its own stretch.gas = [4]andcost = [5]give -1. - A dry tank at exactly 0. The test is
tank < 0, nottank <= 0. Ingas = [3, 1, 1]andcost = [1, 2, 2]the tank is exactly 0 after the last stretch, which is a success. With<=the start would move to station 3, which doesn't exist. - Forgetting the total check. Without it, the second loop returns some candidate even when the trip is impossible. For the second example it would return 2, which fails.
- Not resetting the tank. When the candidate moves, the new trip starts empty. A leftover negative tank would make every later check fail.
- Moving the start to
iinstead ofi + 1. Stationiis the one whose stretch could not be driven, so it is part of the failure. - The first station works. In
gas = [3, 1, 1]andcost = [1, 2, 2]the tank after each stretch is 2, 1 and 0, so the start never moves and the method returns 0.
Testing
gas = [1, 2, 3, 4, 5],cost = [3, 4, 5, 1, 2]gives3.gas = [2, 3, 4],cost = [3, 4, 3]gives-1.gas = [5, 1, 2, 3, 4],cost = [4, 4, 1, 5, 1]gives4.gas = [5],cost = [4]gives0.gas = [4],cost = [5]gives-1.gas = [3, 1, 1],cost = [1, 2, 2]gives0.
