Skip to main content
CodePeetCodePeet
CodePeet 150

Gas Station

MEDIUMProblemSolveExternal Links

Description

There are n gas stations along a circular route. Each station i provides gas[i] units of fuel, and it costs cost[i] units of fuel to travel from station i to station i + 1 (wrapping around to station 0 after station n-1).

You have a car with an unlimited gas tank that starts empty. You begin the journey at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction. If it is impossible to complete the circuit from any station, return -1.

If a solution exists, it is guaranteed to be unique.

The key challenge is figuring out where to start. Starting at the wrong station means you run out of gas mid-circuit. The right starting station gives you enough surplus fuel in the early legs to survive the deficit legs later.

Examples

Example 1

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

Output: 3

Explanation: Start at station 3 (index 3) with an empty tank:

  • Station 3: fill 4, travel cost 1 → tank = 0 + 4 - 1 = 3
  • Station 4: fill 5, travel cost 2 → tank = 3 + 5 - 2 = 6
  • Station 0: fill 1, travel cost 3 → tank = 6 + 1 - 3 = 4
  • Station 1: fill 2, travel cost 4 → tank = 4 + 2 - 4 = 2
  • Station 2: fill 3, travel cost 5 → tank = 2 + 3 - 5 = 0
  • Arrive back at station 3 with exactly 0 gas. Circuit complete!

Example 2

Input: gas = [2,3,4], cost = [3,4,3]

Output: -1

Explanation: Total gas = 2+3+4 = 9, total cost = 3+4+3 = 10. We have less gas than we need overall (9 < 10), so it is physically impossible to complete the circuit from any starting station. Return -1.

Example 3

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

Output: 4

Explanation: Start at station 4: fill 4, cost 1 → tank = 3. Station 0: fill 5, cost 4 → tank = 4. Station 1: fill 1, cost 4 → tank = 1. Station 2: fill 2, cost 1 → tank = 2. Station 3: fill 3, cost 5 → tank = 0. Complete!

Constraints

  • n == gas.length == cost.length
  • 1 ≤ n ≤ 10^5
  • 0 ≤ gas[i], cost[i] ≤ 10^4

Editorial

Brute Force

Intuition

The most direct approach is to try every gas station as a potential starting point. For each candidate, simulate driving around the entire circuit: fill up at each station, pay the travel cost to the next one, and track the tank level. If the tank ever drops below zero, this starting point fails and we move on to the next one.

Think of it like trying every entrance to a circular highway. At each entrance, you drive all the way around and check if you ever run out of fuel. If you do, that entrance does not work. If you make it all the way around, you have found the answer.

Step-by-Step Explanation

Let's trace through with gas = [1,2,3,4,5], cost = [3,4,5,1,2]:

Step 1: Try starting at station 0. Tank = 0. Fill gas[0]=1, pay cost[0]=3. Tank = 0 + 1 - 3 = -2 < 0. Tank is negative! Cannot even reach station 1. FAIL.

Step 2: Try starting at station 1. Tank = 0. Fill gas[1]=2, pay cost[1]=4. Tank = 0 + 2 - 4 = -2 < 0. FAIL.

Step 3: Try starting at station 2. Tank = 0. Fill gas[2]=3, pay cost[2]=5. Tank = 0 + 3 - 5 = -2 < 0. FAIL.

Step 4: Try starting at station 3. Tank = 0. Fill gas[3]=4, pay cost[3]=1. Tank = 0 + 4 - 1 = 3. Positive! Travel to station 4.

Step 5: At station 4. Fill gas[4]=5, pay cost[4]=2. Tank = 3 + 5 - 2 = 6. Travel to station 0.

Step 6: At station 0. Fill gas[0]=1, pay cost[0]=3. Tank = 6 + 1 - 3 = 4. Travel to station 1.

Step 7: At station 1. Fill gas[1]=2, pay cost[1]=4. Tank = 4 + 2 - 4 = 2. Travel to station 2.

Step 8: At station 2. Fill gas[2]=3, pay cost[2]=5. Tank = 2 + 3 - 5 = 0. Exactly 0! Just enough to complete the circuit.

Step 9: Complete circuit from station 3. Return 3.

Brute Force — Trying Every Station as Starting Point — Watch how we simulate the circuit from each station. Stations 0-2 fail immediately, but station 3 has enough surplus gas to survive the deficit legs of the circuit.

Algorithm

  1. For each starting station start from 0 to n-1:
    • Initialize tank = 0
    • Simulate the full circuit: for j from 0 to n-1:
      • Compute current station index = (start + j) % n
      • Add gas[station] and subtract cost[station] from tank
      • If tank < 0, this start fails. Break and try next start.
    • If we complete all n stations without tank going negative, return start
  2. If no starting station works, return -1

Code

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for (int start = 0; start < n; start++) {
            int tank = 0;
            bool canComplete = true;
            for (int j = 0; j < n; j++) {
                int station = (start + j) % n;
                tank += gas[station] - cost[station];
                if (tank < 0) {
                    canComplete = false;
                    break;
                }
            }
            if (canComplete) return start;
        }
        return -1;
    }
};
class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        n = len(gas)
        for start in range(n):
            tank = 0
            can_complete = True
            for j in range(n):
                station = (start + j) % n
                tank += gas[station] - cost[station]
                if tank < 0:
                    can_complete = False
                    break
            if can_complete:
                return start
        return -1
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int start = 0; start < n; start++) {
            int tank = 0;
            boolean canComplete = true;
            for (int j = 0; j < n; j++) {
                int station = (start + j) % n;
                tank += gas[station] - cost[station];
                if (tank < 0) {
                    canComplete = false;
                    break;
                }
            }
            if (canComplete) return start;
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop tries each of the n stations as a starting point. For each start, the inner loop simulates up to n steps around the circuit. In the worst case (answer is the last station, or no answer exists), we perform n × n = n² iterations.

With n up to 10^5, this is up to 10^10 operations — far too slow for typical time limits.

Space Complexity: O(1)

We use only a few integer variables (start, tank, station index). No additional data structures.

Why This Approach Is Not Efficient

The brute force approach wastes work because it restarts the simulation from scratch for each candidate starting station. When starting from station 0 fails at station 2, we learn nothing useful — we just move to station 1 and repeat the entire simulation.

But there is a powerful insight hidden in the failures:

If starting from station s causes the tank to go negative at station i, then NO station between s and i (inclusive) can be a valid starting point either.

Why? Because starting at any station between s and i means you arrive at station i with even less gas (you miss the fuel from the earlier stations). So we can skip directly to station i + 1 as the next candidate.

Additionally, if the total gas across all stations is at least the total cost, a solution is guaranteed to exist. These two observations let us find the answer in a single pass.

Optimal Approach - Greedy (One Pass)

Intuition

The greedy approach is built on two key insights:

Insight 1 (Skip Ahead): If starting from station s fails at station i (tank goes negative), then no station between s and i can work either. The next candidate must be station i + 1. This is because reaching station i from any station between s and i would give us even less fuel than starting at s (since we miss the fuel from the skipped stations).

Insight 2 (Feasibility): If the total gas ≥ total cost (sum of all gas[i] - cost[i] ≥ 0), then a valid starting point must exist. If total gas < total cost, no starting point can work.

Combining these insights: we scan once from left to right, tracking currGas (running tank from current candidate start) and totalGas (overall feasibility). Whenever currGas drops below zero, we reset the candidate start to the next station. At the end, if totalGas ≥ 0, the last candidate is the answer.

Think of it like walking along a circular trail with water stations. If you run out of water at some point, you know starting anywhere earlier on this stretch would be even worse. So you teleport to the next station and try from there. If there is enough total water on the trail, one starting point is guaranteed to work.

Step-by-Step Explanation

Let's trace with gas = [1,2,3,4,5], cost = [3,4,5,1,2]:

First, compute the net gas at each station: diff[i] = gas[i] - cost[i] = [-2, -2, -2, 3, 3].

Step 1: Initialize: totalGas = 0, currGas = 0, start = 0.

Step 2: Station 0: diff = -2. currGas = 0 + (-2) = -2. totalGas = -2. Since currGas < 0, starting from station 0 fails. Reset: start = 1, currGas = 0.

Step 3: Station 1: diff = -2. currGas = 0 + (-2) = -2. totalGas = -4. currGas < 0 again. Reset: start = 2, currGas = 0.

Step 4: Station 2: diff = -2. currGas = 0 + (-2) = -2. totalGas = -6. currGas < 0 yet again. Reset: start = 3, currGas = 0.

Step 5: Station 3: diff = +3. currGas = 0 + 3 = 3. totalGas = -3. currGas ≥ 0! Start candidate stays at 3.

Step 6: Station 4: diff = +3. currGas = 3 + 3 = 6. totalGas = 0. currGas ≥ 0. Start stays at 3.

Step 7: Scan complete. totalGas = 0 ≥ 0, so a valid circuit exists. Return start = 3.

Greedy One Pass — Scanning Net Gas and Resetting Start Candidate — Watch how we scan the net-gas array once. Each time the running tank goes negative, we reset the start candidate to the next station. The totalGas tracker confirms feasibility at the end.

Algorithm

  1. Initialize three variables: totalGas = 0, currGas = 0, start = 0
  2. For each station i from 0 to n-1:
    • Compute diff = gas[i] - cost[i]
    • Add diff to both totalGas and currGas
    • If currGas < 0:
      • Set start = i + 1 (skip to next station)
      • Reset currGas = 0
  3. After the loop:
    • If totalGas ≥ 0, return start (a valid circuit exists starting there)
    • Otherwise, return -1 (no valid starting point exists)

Code

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalGas = 0, currGas = 0, start = 0;

        for (int i = 0; i < (int)gas.size(); i++) {
            int diff = gas[i] - cost[i];
            totalGas += diff;
            currGas += diff;

            if (currGas < 0) {
                start = i + 1;
                currGas = 0;
            }
        }

        return totalGas >= 0 ? start : -1;
    }
};
class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        total_gas = 0
        curr_gas = 0
        start = 0

        for i in range(len(gas)):
            diff = gas[i] - cost[i]
            total_gas += diff
            curr_gas += diff

            if curr_gas < 0:
                start = i + 1
                curr_gas = 0

        return start if total_gas >= 0 else -1
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, currGas = 0, start = 0;

        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            totalGas += diff;
            currGas += diff;

            if (currGas < 0) {
                start = i + 1;
                currGas = 0;
            }
        }

        return totalGas >= 0 ? start : -1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the gas and cost arrays exactly once. Each station is visited once, and at each station we perform O(1) work (compute diff, update running sums, possibly reset start). Total: n iterations × O(1) = O(n).

With n up to 10^5, this completes in about 10^5 operations — comfortably within time limits.

Space Complexity: O(1)

We use only three integer variables (totalGas, currGas, start). No additional arrays or data structures. The algorithm works entirely in-place on the input arrays.