Course4all
Join us on telegram
Home/dsa/Greedy/Gas Station

Gas Station

Master this topic with zero to advance depth.

Gas Station

There are n gas stations along a circular route, where the amount of gas at the ithi^{th} station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ithi^{th} station to its next (i+1)th(i + 1)^{th} station.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Circular Logic

If you start at index ii, you must be able to visit i+1,i+2,...,n−1,0,1,...,i−1i+1, i+2, ..., n-1, 0, 1, ..., i-1.

Medium

Examples

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

Start at station 3 (index 3). Fill 4 units of gas. Your tank = 4. Cost to next = 1. Remaining = 3. Final tank check covers the loop.

Approach 1

Level I: Brute Force (Simulation)

Intuition

Try starting from every single gas station and simulate the journey. If you can complete the circle without the tank becoming negative, that's your starting station.

Visual Representation

Stations: [S0, S1, S2] Try S0: S0 -> S1 -> S2 -> S0 (Check tank >= 0 at each step) Try S1: S1 -> S2 -> S0 -> S1 Try S2: S2 -> S0 -> S1 -> S2

Thought Process

  1. Iterate start from 00 to n−1n-1.
  2. For each start, initialize tank = 0.
  3. Iterate i from 00 to n−1n-1 to visit all stations using (start + i) % n.
  4. If tank < 0 at any point, stop and try next start.

Pattern: Circular Simulation

⏱ O(N^2)💾 O(1)

Detailed Dry Run

gas=[1,2], cost=[2,1] S0: tank=1-2=-1. FAIL. S1: tank=2-1=1. Next: tank=1+(1-2)=0. SUCCESS!

java
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int tank = 0, count = 0, j = i;
            while (count < n) {
                tank += gas[j] - cost[j];
                if (tank < 0) break;
                j = (j + 1) % n; count++;
            }
            if (count == n) return i;
        }
        return -1;
    }
}
Approach 2

Level II: Greedy with Total Sum Check

Intuition

Before attempting a simulation, check if a solution even exists. If ∑gas<∑cost\sum gas < \sum cost, it is mathematically impossible to complete the circuit regardless of where you start.

Thought Process

  1. Calculate totalGas and totalCost.
  2. If totalGas < totalCost, return -1.
  3. Otherwise, use the greedy property: if you fail to reach station BB starting from AA, any station between AA and BB will also fail to reach BB.

Pattern: Pruning / Feasibility Check

⏱ O(N)💾 O(1)

Detailed Dry Run

gas=[1,2,3], cost=[2,2,2]. Total gas=6, cost=6. Possible. Start S0: tank=1-2=-1. FAIL. Reset start to S1. Start S1: tank=2-2=0. OK. Start S2: tank=0+(3-2)=1. OK. Return S1.

java
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sumG = 0, sumC = 0;
        for (int i = 0; i < gas.length; i++) { sumG += gas[i]; sumC += cost[i]; }
        if (sumG < sumC) return -1;
        int start = 0, tank = 0;
        for (int i = 0; i < gas.length; i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) { start = i + 1; tank = 0; }
        }
        return start;
    }
}
Approach 3

Level III: Optimal Greedy (One-Pass)

Intuition

We can combine the total sum check into the main loop. Track totalDiff as we go. If totalDiff is negative at the end, return -1. Otherwise, the last valid start candidate is guaranteed to work.

Visual Representation

Indices: [ 0, 1, 2, 3, 4] Diffs: [-2, -2, -2, 3, 3] Loop: i=0: tank=-2. Fail. start=1, tank=0. i=1: tank=-2. Fail. start=2, tank=0. i=2: tank=-2. Fail. start=3, tank=0. i=3: tank=3. OK. i=4: tank=6. OK. TotalDiff = 0 >= 0. Result: start index 3.

Thought Process

  1. Use totalTank to keep running sum of all (gas[i] - cost[i]).
  2. Use currentTank to track gas from current start candidate.
  3. If currentTank drops below 0, the current start (and all stations between it and i) is invalid. Reset currentTank and set start = i + 1.
  4. Final answer: totalTank >= 0 ? start : -1.

Pattern: Candidate Elimination

⏱ O(N)💾 O(1)

Detailed Dry Run

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

idiffcurTanktotalTankstart
0-2-2 (Reset)-21
1-2-2 (Reset)-42
2-2-2 (Reset)-63
333-33
43603
totalTank=0. Return 3.
java
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalTank = 0, currentTank = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            totalTank += diff;
            currentTank += diff;
            if (currentTank < 0) {
                start = i + 1;
                currentTank = 0;
            }
        }
        return totalTank >= 0 ? start : -1;
    }
}
← Previous QuestionJump Game II
Next Question →Partition Labels