Gas Station

Gas Station feels like a road trip puzzle. There is a ring of stations around a track. Each one gives you some fuel and charges you some fuel to reach the next. You want one starting station from which you can drive the full loop. The slow way tries starting from every station. The fast way solves it in one pass. The leap there is the real test.

🎯 The Problem

You get two arrays of the same length and must find one valid starting station for the loop.

• gas[i] is the fuel you pick up at station i.
• cost[i] is the fuel needed to drive from station i to the next one.
• The stations form a circle. After the last one you loop back to the first.
• You start with an empty tank.
• Return the index of a station you can begin from and drive all the way around once.
• If no such station exists, return -1. The valid start is unique when it exists.

Let us say gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2]. Starting at station 3 works. So the answer is 3.

Input:  gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3

Explanation: Start at station 3. Tank fills and never drops below zero around the loop.

The key number at each station is the net fuel, which is gas[i] - cost[i]. If it is positive you gain fuel there. If it is negative you lose fuel. Here is the ring with the net at each station.

🐢 Approach 1: Try Every Start (Brute Force)

Pick each station as a possible start and simulate the full loop.

The idea:

• Try station 0 first. Drive the whole circle and track the tank.
• If the tank never drops below zero, that station is the answer.
• If it drops below zero, try station 1, then 2, and so on.

How it works:

• Outer loop picks the starting station.
• Inner loop drives the loop from that start and adds each net.
• Stop a start early the moment the tank goes negative.

Why it is weak:

• For each start you may drive the whole loop again.
• That is a loop inside a loop.
• Time grows as O(n²). Too slow on many stations.

Here is the try-every-start code:

def can_complete_circuit(gas, cost):
    n = len(gas)
    for start in range(n):
        tank = 0
        for step in range(n):
            i = (start + step) % n
            tank += gas[i] - cost[i]
            if tank < 0:
                break
        else:
            return start
    return -1

⚡ Approach 2: One Pass With Total and Tank (Best)

The idea in one line: one sweep tells you both whether an answer exists and where it starts.

The idea:

• The total of all nets says if the loop is possible at all.
• The running tank says where a valid start begins.
• A net is gas[i] - cost[i], the fuel you gain or lose.

How it works:

• Sum every net into total. If the whole system has less gas than cost, no start works.
• Keep a running tank from the current start. Add each net to it.
• When tank drops below zero, the current start fails. Move start to the next station and reset tank to 0.
• At the end, return start if total >= 0, else -1.

Why it is fast:

• You walk the stations only once. So it is O(n).
• You can skip every failed station in between. They had even less fuel for that same stretch, so none of them could survive it.
• Greedy here means you jump the start forward past every station that just failed and trust it.

Here is a dry run on gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]. Watch the tank reset and the start move to 3.

Steps to Solve

1. Keep a total of all nets and a running tank, both starting at 0. Set start = 0.
2. Walk through the stations once. Compute each net as gas[i] - cost[i].
3. Add the net to both total and tank.
4. If tank drops below zero, set start to i + 1 and reset tank to 0.
5. After the loop, if total is negative, return -1, because no start can finish.
6. Otherwise return start.

#include <stdio.h>

int canCompleteCircuit(int gas[], int cost[], int n) {
    int total = 0;   // net fuel across all stations
    int tank = 0;    // running tank from the current start
    int start = 0;   // candidate starting station
    for (int i = 0; i < n; i++) {
        int net = gas[i] - cost[i];
        total += net;
        tank += net;
        if (tank < 0) {     // current start failed
            start = i + 1;  // try the next station
            tank = 0;       // empty tank again
        }
    }
    return total >= 0 ? start : -1;  // -1 if not enough fuel overall
}

int main(void) {
    int gas[]  = {1, 2, 3, 4, 5};
    int cost[] = {3, 4, 5, 1, 2};
    int n = 5;
    printf("%d\n", canCompleteCircuit(gas, cost, n));
    return 0;
}

3

#include <iostream>
#include <vector>
using namespace std;

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < (int)gas.size(); i++) {
        int net = gas[i] - cost[i];
        total += net;
        tank += net;
        if (tank < 0) {     // current start failed
            start = i + 1;  // try the next station
            tank = 0;       // empty tank
        }
    }
    return total >= 0 ? start : -1;
}

int main() {
    vector<int> gas  = {1, 2, 3, 4, 5};
    vector<int> cost = {3, 4, 5, 1, 2};
    cout << canCompleteCircuit(gas, cost) << endl;
    return 0;
}

3

public class GasStation {
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0, tank = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            int net = gas[i] - cost[i];
            total += net;
            tank += net;
            if (tank < 0) {     // current start failed
                start = i + 1;  // try the next station
                tank = 0;       // empty tank
            }
        }
        return total >= 0 ? start : -1;
    }

    public static void main(String[] args) {
        int[] gas  = { 1, 2, 3, 4, 5 };
        int[] cost = { 3, 4, 5, 1, 2 };
        System.out.println(canCompleteCircuit(gas, cost));
    }
}

3

def can_complete_circuit(gas, cost):
    total = 0   # net fuel across all stations
    tank = 0    # running tank from the current start
    start = 0   # candidate starting station
    for i in range(len(gas)):
        net = gas[i] - cost[i]
        total += net
        tank += net
        if tank < 0:        # current start failed
            start = i + 1   # try the next station
            tank = 0        # empty tank again
    return start if total >= 0 else -1


gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(can_complete_circuit(gas, cost))

3

function canCompleteCircuit(gas, cost) {
  let total = 0; // net fuel across all stations
  let tank = 0;  // running tank from the current start
  let start = 0; // candidate starting station
  for (let i = 0; i < gas.length; i++) {
    const net = gas[i] - cost[i];
    total += net;
    tank += net;
    if (tank < 0) {     // current start failed
      start = i + 1;    // try the next station
      tank = 0;         // empty tank
    }
  }
  return total >= 0 ? start : -1;
}

const gas = [1, 2, 3, 4, 5];
const cost = [3, 4, 5, 1, 2];
console.log(canCompleteCircuit(gas, cost));

3

Let us walk through the Python version line by line, because two ideas are packed into one short loop.

total = 0, tank = 0, start = 0 set up the three numbers. total sums every net to decide if the trip is even possible. tank is the fuel since the current start. start is the station we currently believe is the answer.

for i in range(len(gas)): walks every station once. There is no inner loop, which is exactly why this is fast.

net = gas[i] - cost[i] is the fuel you gain or lose at this station. Positive means you collect more than you spend.

total += net and tank += net add the net to both running sums. total never resets. tank does.

if tank < 0: is the failure check. If the tank goes negative, you cannot reach this station from the current start. So that start, and every station before this one in the stretch, is ruled out.

start = i + 1 jumps the start to the next station. tank = 0 empties the tank for the fresh start.

return start if total >= 0 else -1 gives the final answer. If the whole system had enough fuel, start is correct. If not, no start works, so return -1.

⏱️ Time and Space Complexity

The brute force tries every station as a start and may drive the full loop each time, so it is O(n²). The greedy way keeps three numbers and one loop. So it trades nothing and still wins. That takes the time all the way down to O(n) with O(1) extra space.

🧩 Key Takeaways

• ✅ The net at each station is gas[i] - cost[i], the fuel you gain or lose there.
• ✅ If the total of all nets is negative, no start can finish, so return -1.
• ✅ When the running tank goes below zero, move the start to the next station and reset the tank.
• ✅ You can skip all the failed stations in between, because they had even less fuel for that stretch.
• ✅ This runs in O(n) time with O(1) extra space, beating the O(n²) brute force.

🚀 What’s Next?

• Jump Game
• Partition Labels