Home/Questions/Q 3528
Next
In Process

RTSALL Latest Articles

Abhishek
Begginer
Asked: 2026-09-11T09:52:35-05:00 In: ,

Gas Station Circular Tour: Mathematical proof of why a single pass in O(N) is sufficient

There are n gas stations along a circular route, where the amount of gas at the i-th station is gas[i]. It costs cost[i] of gas to travel from station i to i + 1. You begin the journey with an empty tank at one of the gas stations.

The standard greedy algorithm claims that if the total gas is at least the total cost, a solution is guaranteed to exist, and whenever your running tank drops below 0 at station i, you can safely restart your search from station i + 1. Why are we allowed to skip all intermediate stations between start and i?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Anonymous
    Begginer

    The Gas Station problem is one of the most elegant examples of the Greedy Elimination Proof. Let’s break down the mathematical invariant that allows you to skip stations with 100% confidence.

    1. The Two Fundamental Theorems

    Theorem 1: Total Balance Invariant

    If $sum gas[i] ge sum cost[i]$, there is guaranteed to be at least one valid starting station that completes the entire circuit.

    Why? Because the total net balance $sum (gas[i] – cost[i]) ge 0$. If you graph the cumulative fuel sum along the circle, the lowest dip (the absolute minimum point on the graph) is the optimal starting point! Starting right after that lowest dip means your tank will never dip below zero!

    Theorem 2: The Greedy Skip Invariant

    Suppose you start at station A and successfully reach station B, but you fail to travel from B to B + 1 (your tank drops below 0).

    Claim: No station C between A and B (i.e. $A le C le B$) can be the starting station!

    Proof:

    1. Because you started at A and reached C, the gas you had in your tank upon arriving at C was $ge 0$.
    2. Even with that bonus leftover gas from before C, you still starved and died at B!
    3. If you were to start at C from scratch (with an empty tank, zero bonus gas), you would run out of fuel at or before station B!

    Therefore, every single station from A to B is mathematically disqualified in one fell swoop! The next possible candidate can only be B + 1.

    Clean Python 3.12 Implementation

    def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    """Finds starting gas station index in single pass O(N) time."""
    total_tank = 0
    curr_tank = 0
    starting_station = 0

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

        # If we run out of gas at station i
        if curr_tank < 0:
            # Pick the next station as candidate start
            starting_station = i + 1
            # Reset current tank to 0
            curr_tank = 0

    # If total gas is less than total cost, impossible to complete circle
    return starting_station if total_tank >= 0 else -1

    Complexity Breakdown

    • Time Complexity: O(N). Exactly one single pass through the array. Zero nested loops.
    • Space Complexity: O(1). Exactly 3 scalar integers tracking running totals.
    • 0
  2. Anonymous
    Begginer

    Here is the clean C++20 Single-Pass Greedy solution for the Gas Station problem.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>

int canCompleteCircuit(const std::vector<int>& gas, const std::vector<int>& cost) {
    int total_tank = 0;
    int curr_tank = 0;
    int start_station = 0;

    for (size_t i = 0; i < gas.size(); ++i) {
        int diff = gas[i] - cost[i];
        total_tank += diff;
        curr_tank += diff;

        if (curr_tank < 0) {
            // Greedy restart at next station
            start_station = i + 1;
            curr_tank = 0;
        }
    }
    return total_tank >= 0 ? start_station : -1;
}

int main() {
    std::vector<int> gas  = {1, 2, 3, 4, 5};
    std::vector<int> cost = {3, 4, 5, 1, 2};

    int start = canCompleteCircuit(gas, cost);
    std::cout << "Valid Starting Station Index: " << start << "n"; // Station 3 (0-indexed)
    return 0;
}

    Complexity: Strictly O(N) time and O(1) auxiliary space.

    • 0