Gas Station Problem: Greedy Circular Array Solution with Step-by-Step Explanation

The Gas Station Problem is a popular algorithmic challenge often asked in coding interviews and online assessment tests. It involves determining whether a car can complete a circular route given the fuel available at each gas station and the cost it takes to travel between them. This problem is a perfect demonstration of the greedy algorithm technique applied on circular arrays.

In this article, we will explain the problem in detail, explore the greedy strategy, analyze its complexity, and provide code examples with visualizations.

Table of Contents

Problem Definition

We are given two integer arrays of equal length:

gas[i] → The amount of fuel provided at station i
cost[i] → The amount of fuel required to travel from station i to i+1

The task is to determine the index of the gas station from which the car can start with an empty fuel tank and complete the full circular route, or return -1 if no such station exists.

Constraints:

If the total fuel available is less than the total cost of the journey, there is no valid solution.
There can be exactly one unique starting solution if a solution exists.

Example Walkthrough

Let us consider an example:

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

Step-by-step analysis:

Total gas = 1+2+3+4+5 = 15
Total cost = 3+4+5+1+2 = 15
Since gas == cost, a solution is possible.
Try starting from station 0:
1. Fuel left after first travel = 1 – 3 = -2 → Cannot continue from station 0.
Try from station 3 (gas=4):
1. 4 – 1 = 3
2. 3 + 5 – 2 = 6
3. 6 + 1 – 3 = 4
4. 4 + 2 – 4 = 2
5. 2 + 3 – 5 = 0 → Successfully completed!

Answer: 3 (Start from station index 3).

Greedy Solution Approach

Instead of checking each starting point (which would be O(n^2)), we can solve this efficiently using a greedy approach:

Check if sum(gas) < sum(cost), if true → return -1.
Maintain two variables:
- totalTank: net amount of fuel over the journey
- currentTank: fuel in the tank when traversing
Iterate over stations:
- Add gas[i] - cost[i] to currentTank.
- If currentTank goes negative, the journey cannot start from previous stations. Reset starting index to i+1, and reset currentTank = 0.
The candidate answer is the last starting index after completing iteration.

This works because if the car cannot reach i+1 from the current start, then no station between the start and i can be the solution.

Python Implementation


def canCompleteCircuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1

    start, tank = 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start

Testing the function:


gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(canCompleteCircuit(gas, cost))  # Output: 3

Visualizing the Running Total

The greedy algorithm resets the starting station whenever the tank goes negative. Let’s visualize:

Complexity Analysis

Time Complexity: O(n), since we only iterate the array once.
Space Complexity: O(1), using only counters.

Interactive Example

Try running this interactive Python version where you can change the inputs:


def try_gas_station():
    gas = list(map(int, input("Enter gas array: ").split()))
    cost = list(map(int, input("Enter cost array: ").split()))
    print("Starting station index:", canCompleteCircuit(gas, cost))

# Example Input:
# Enter gas array: 1 2 3 4 5
# Enter cost array: 3 4 5 1 2
# Output: 3

Key Takeaways

The Gas Station Problem is solved efficiently with a greedy algorithm in linear time.
The critical trick is resetting the start index whenever fuel in the current path runs out.
Only one valid starting point exists if the solution is possible.
This problem demonstrates circular array traversal and greedy decision-making.

This algorithmic pattern is valuable for solving many coding interview challenges involving resource deficits spread across circular paths or distributed elements.