Start learning free

LESSON 463 OF 540 · GREEDY

Gas Station in Kotlin: O(n) Greedy with O(1) Extra Space

Practice O(n) Read the full explanation

There are n gas stations on a circular route, numbered from 0 to n - 1. Station i has gas[i] units of gas, and driving from station i to the next station costs cost[i] units. After the last station, n - 1, the next one is station 0 again.

Your car's tank has no size limit, and it starts empty at one of the stations. At every station you take all of its gas, then drive on to the next station, going around the circle in increasing order. You can drive a stretch only if the tank holds at least its cost.

Return the index of the station to start from so that you drive all the way around the circle once and get back to it, or -1 if no start works. When a start works, it is the only one.

 

Example 1:

Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Explanation: Start at station 3 and take its 4 units: the tank has 4.
Drive to station 4 (cost 1) and take 5: 4 - 1 + 5 = 8.
Drive to station 0 (cost 2) and take 1: 8 - 2 + 1 = 7.
Drive to station 1 (cost 3) and take 2: 7 - 3 + 2 = 6.
Drive to station 2 (cost 4) and take 3: 6 - 4 + 3 = 5.
Drive back to station 3: it costs 5, and the tank has exactly 5.
From any other start, the tank runs dry on the way.

Example 2:

Input: gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1
Explanation: The stations have 2 + 3 + 4 = 9 units of gas in all, but the trip around
costs 3 + 4 + 3 = 10, so no start can work.

Example 3:

Input: gas = [5, 1, 2, 3, 4], cost = [4, 4, 1, 5, 1]
Output: 4
Explanation: From station 0 you reach station 1 with 5 - 4 = 1, but 1 + 1 = 2 is less than
the 4 it costs to go on. Starting at station 1 instead is no better: you would be there
with an empty tank instead of 1. From station 2 you reach station 3 with 2 - 1 = 1, but
1 + 3 = 4 is less than 5, and station 3 can't go on alone either. From station 4 the tank
has 3 at station 0, 4 at station 1, 1 at station 2, 2 at station 3 and 0 back at station 4.

 

Constraints:

  • n == gas.length == cost.length
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104
  • At most one station works as the start.

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

The tutorial is greedy. First it adds up gas[i] - cost[i] over all the stations: if the total is negative, the trip around costs more than all the gas there is, and no start can work. Otherwise it drives once from station 0 to the last station, keeping the gas in the tank and a candidate start, first 0. Whenever the tank drops below 0 on the stretch after station i, the car couldn't have driven it: the candidate moves to station i + 1, and the tank starts again from empty. At the end, the candidate is the answer.

Why skipping all the stations from start to i is safe: starting at start, the car reached each of them with 0 or more gas in the tank. Starting at one of them instead means being there with an empty tank, which is never better, so the tank would still drop below 0 after station i. None of them can be the start, and the next station to try is i + 1.

Why the last candidate works: from it, the car reaches the end of the list without running dry. Each stretch it skipped before it loses gas overall, but the total isn't negative, so the gas left in the tank at the end is at least what all of them lose together. Inside a skipped stretch the tank only goes below 0 at its very end, so with that gas the car gets through each of them, and back to the start.

STEP 1 OF 13
    Ctrl + Enter to check

    KOTLIN · GREEDY

    Gas Station in Kotlin, explained

    Problem overview

    Stations sit on a circular route. Station i gives gas[i] units, and driving from station i to the next one costs cost[i]. The tank has no size limit and starts empty at the station you choose. At each station you take all its gas, then drive on. canCompleteCircuit(gas, cost) returns the index of the start from which you can go all the way around and come back, or -1 if there is none. At most one start works.

    For gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2] the answer is 3. Starting there you take 4, drive to station 4 and take 5 (tank 8), drive to station 0 and take 1 (tank 7), and so on, arriving back at station 3 with exactly 5 for the last stretch. 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

    The obvious plan tries every start and simulates the whole loop, which is O(n²) for up to 100,000 stations. A greedy idea does it in one pass, using two facts.

    Fact 1: a total check. 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 works. If it is not negative, a start exists.

    Fact 2: skipping failed starts. Drive once from station 0 to the last station, keeping the tank and a candidate start (first 0). When the tank drops below 0 on the stretch after station i, the car could not have driven it. Stations start to i cannot be the start either: from start the car reached each of them with 0 or more gas, and starting at one of them means arriving with an empty tank, which is never better, so it would run dry at the same place. So the next candidate is i + 1, with an empty tank.

    Why is the last candidate right? From it, the car reaches the end of the list without running dry. Each stretch skipped before it loses gas overall, but the total is not negative, so the gas left at the end covers everything the skipped stretches lose together. Inside a skipped stretch the tank only went below 0 at its very end, so with that spare gas the car gets through each of them and back to the start.

    Step by step

    1. Station count. val n = gas.size. The route is a circle: after station n - 1 comes station 0.
    2. The total. A var total starts at 0, and a loop over 0 until n adds gas[i] - cost[i]: what station i gives minus what the next stretch costs.
    3. Reject impossible trips. If total < 0, return -1 right away.
    4. Candidate and tank. var start = 0 and var tank = 0. Both change in the loop.
    5. One drive. Loop over 0 until n and add gas[i] - cost[i] to tank: after this line the tank holds the gas on arriving at the next station.
    6. Dry tank. If tank < 0, move start to i + 1 and set tank back to 0. Exactly 0 is fine: the car arrives empty and takes the next station's gas.
    7. Return start.

    The solution in Kotlin

    class Solution {
    fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
        val n = gas.size
        var total = 0
        for (i in 0 until n) {
            total += gas[i] - cost[i]
        }
        if (total < 0) {
            return -1
        }
        var start = 0
        var tank = 0
        for (i in 0 until n) {
            tank += gas[i] - cost[i]
            if (tank < 0) {
                start = i + 1
                tank = 0
            }
        }
        return start
    }
}

    Kotlin details worth knowing:

    • 0 until n excludes n. It is the right range for array indexes. 0..n would read gas[n] and throw ArrayIndexOutOfBoundsException.
    • var for values that change. total, start and tank are reassigned in the loops. n never changes, so it is a val.
    • gas.size, not length. Arrays in Kotlin have size.
    • No overflow here. The largest possible sum is 100,000 × 10,000 = 1,000,000,000 in absolute value, which fits in an Int (the limit is 2,147,483,647).

    Tracing the examples

    For the first example, each line shows gas[i] - cost[i], the tank after it (or dry), and the candidate afterwards:

    i=0 gas-cost=-2 tank=dry start=1
i=1 gas-cost=-2 tank=dry start=2
i=2 gas-cost=-2 tank=dry start=3
i=3 gas-cost=3 tank=3 start=3
i=4 gas-cost=3 tank=6 start=3

    The differences sum to 0, so a start exists, and the candidate that survives the pass is 3. For gas = [5, 1, 2, 3, 4] and cost = [4, 4, 1, 5, 1], the tank before any reset at each station is:

    i=0 diff=1  tank=1  start=0
i=1 diff=-3 tank=-2 start=2
i=2 diff=1  tank=1  start=2
i=3 diff=-2 tank=-1 start=4
i=4 diff=3  tank=3  start=4

    The tank goes negative at stations 1 and 3, which moves the candidate to 2 and then to 4. The function returns 4.

    Complexity

    Time: two passes over the stations, each with constant work per station: O(n).

    Space: a few integers: O(1) extra.

    Edge cases and common mistakes

    • One station. gas = [5], cost = [5] returns 0, since the trip costs exactly the gas. With cost = [6] the total is negative and the answer is -1.
    • Exactly 0 is allowed. Test tank < 0, not tank <= 0. Using <= would reject starts that arrive with an empty tank.
    • Skipping the total check. Without it, the loop returns some candidate even when no start works. For the second example the loop ends with start at 2 instead of returning -1.
    • Moving to i instead of i + 1. Station i was reached and its stretch failed, so it cannot be the start.
    • Forgetting to reset the tank. The new candidate begins with an empty tank, like the first one.

    Testing

    gas [1, 2, 3, 4, 5], cost [3, 4, 5, 1, 2]  gives 3
gas [2, 3, 4],       cost [3, 4, 3]        gives -1
gas [5, 1, 2, 3, 4], cost [4, 4, 1, 5, 1]  gives 4
gas [5],             cost [5]              gives 0
gas [5],             cost [6]              gives -1
gas [3, 1],          cost [1, 3]           gives 0
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free