Start learning free

LESSON 462 OF 539 · GREEDY

Gas Station in C#: O(n) Greedy with a Moving Start

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

    C# · GREEDY

    Gas Station in C#, explained

    Problem overview

    There are n gas stations on a circular route. Station i gives gas[i] units, and driving from station i to the next one costs cost[i]. After station n - 1 the route continues at station 0. The tank has no size limit and starts empty. At each station you take all its gas, then drive on, and a stretch is allowed only if the tank holds at least its cost.

    The method CanCompleteCircuit returns the index of the station to start from so that a full lap works, or -1 if no start does. At most one start works.

    In the first example, gas = {1, 2, 3, 4, 5} and cost = {3, 4, 5, 1, 2}. Starting at station 3 the tank holds 4, then 8 at station 4, 7 at station 0, 6 at station 1, 5 at station 2, and exactly the 5 needed for the last stretch. The answer is 3. In the second example the gas totals 9 and the lap costs 10, so the answer is -1.

    The lesson asks for O(n) time and O(1) extra space.

    Approach: one lap decides, one pass finds the start

    Trying every station as a start and simulating a lap is O(n²). The greedy solution needs two observations.

    The total decides whether any start exists. Add up gas[i] - cost[i] over all stations. If the sum is negative, the lap costs more than all the gas there is, so no start works and the answer is -1. If it isn't negative, a start exists, and the problem says it is unique.

    A failure rules out a whole stretch of candidates. Drive from a candidate start, keeping the tank. If the tank drops below 0 on the stretch after station i, the car could not have driven it. Every station between start and i is ruled out too, because the car reached each of them with 0 or more gas. Starting at one of them means being there with an empty tank, which is never better, so the tank would still go negative at i. The next candidate is i + 1, with an empty tank.

    After one pass, the last candidate is the answer. It reaches the end of the list without running dry. The stretches skipped before it lose gas overall, but the total isn't negative, so the gas left at the end covers what all those stretches lose, and the car gets back around to the start.

    Tracing the pass

    For gas = {1, 2, 3, 4, 5} and cost = {3, 4, 5, 1, 2}, this is the tank and the candidate after each station:

    i=0 tank=0 start=1 (ran dry, start moves)
i=1 tank=0 start=2 (ran dry, start moves)
i=2 tank=0 start=3 (ran dry, start moves)
i=3 tank=3 start=3
i=4 tank=6 start=3

    Stations 0, 1 and 2 each fail at once (the differences are -2, -2 and -2), and the candidate moves to 3. From station 3 the tank never goes negative. For gas = {5, 1, 2, 3, 4} and cost = {4, 4, 1, 5, 1}, the candidate moves to 2 after station 1 and to 4 after station 3, and the answer is 4:

    i=0 tank=1 start=0
i=1 tank=0 start=2 (ran dry, start moves)
i=2 tank=1 start=2
i=3 tank=0 start=4 (ran dry, start moves)
i=4 tank=3 start=4

    Step by step

    1. Store the number of stations gas.Length in n.
    2. Create total, starting at 0, to add up what each station gives minus what the following stretch costs.
    3. Loop i from 0 to n - 1 and add gas[i] - cost[i] to total. A station with less gas than its stretch costs contributes a negative number.
    4. Return -1 if total is negative. All the gas can't pay for the lap. Otherwise a start exists.
    5. Create start at 0 and tank at 0. Station 0 is tried first, and the start only moves forward when it fails.
    6. Loop over the stations again and add gas[i] - cost[i] to tank. Afterwards, tank is the gas left on arriving at the next station.
    7. If tank is negative, the stretch could not be driven from start. Exactly 0 is fine: the car arrives empty and still takes the next station's gas.
    8. Move start to i + 1, the first station not yet ruled out, and reset tank to 0, because the trip begins again there.
    9. Return start after the loop.

    The solution in C#

    class Solution {
    public int CanCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.Length;
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += gas[i] - cost[i];
        }
        if (total < 0) {
            return -1;
        }
        int start = 0;
        int tank = 0;
        for (int i = 0; i < n; i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return start;
    }
}

    The C# details worth knowing:

    • Arrays. gas.Length is a property and gives the array's fixed size. The two arrays have the same length, so one loop bound serves both.
    • Overflow. int arithmetic wraps silently in C# unless the code is in a checked context. Here it can't happen: with up to 100,000 stations and values up to 10,000, the largest possible sum of gas is 1,000,000,000, below int.MaxValue (2,147,483,647). With 100,000 stations of 10,000 gas and cost 0, the method returns 0 and the sum is 1000000000.
    • Compound assignment. total += gas[i] - cost[i] adds the difference in place, and the subtraction happens first.
    • Two loops, two scopes. Both loops declare int i. That is allowed because each i exists only inside its own for.
    • The candidate stays a valid index. When total is not negative, start never ends up equal to n: that would mean every stretch of the lap had failed in turn, which would make the total negative.

    Complexity

    Time: O(n). Two loops over the stations, each doing constant work per iteration. No station is revisited, because the candidate only moves forward.

    Space: O(1). Four integers: n, total, start and tank.

    Edge cases and common mistakes

    • A single station. gas = {5} and cost = {4} returns 0, and gas = {4} with cost = {5} returns -1. When gas equals cost, as in {3} and {3}, the answer is 0.
    • Everything zero. gas = {0, 0} and cost = {0, 0} returns 0: the total is 0, so a start exists, and nothing ever makes the tank negative.
    • A tank of exactly 0 is fine. Using tank <= 0 as the failure test would move the start wrongly. For gas = {3} and cost = {3} it would turn the start into 1, which is not even a station.
    • Skipping the total check. Without it, the second loop returns some index even when no start works. For gas = {2, 3, 4} and cost = {3, 4, 3} the correct answer is -1.
    • Forgetting to reset the tank. The new start begins empty. Carrying the negative tank over would reject good starts.
    • Restarting at i instead of i + 1. Station i is where the car just failed to leave, so it can't be the next candidate.
    • Testing each start with a full lap. It works but takes O(n²), too slow for 100,000 stations.

    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 = {4} gives 0.
    • gas = {4}, cost = {5} gives -1.
    • gas = {0, 5}, cost = {3, 2} gives 1.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free