Gas Station

mosesg1123
Jun 14
5 min read

The "Gas Station" problem is one of those deceptively simple problems that really tests your understanding of greedy strategies and circular arrays. It shows up frequently in interviews because it blends math, algorithmic reasoning, and a need for linear-time optimization. Whether you're optimizing a delivery route or designing a resource allocation system, this kind of thinking comes in handy.

Problem Statement

There are n gas stations arranged in a circle. Each station has gas[i] units of gas, and it costs cost[i] units of gas to travel from station i to station i + 1 (with the last station connecting back to the first).

You have a car with an unlimited gas tank, but you start with an empty tank at one of the stations.

Return the starting station index if you can complete the circuit once in the clockwise direction. If you can’t, return -1.

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

Example 1:

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

Example 2:

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

1. Clarify Requirements Before Jumping Into Code

Can we start at any gas station? → Yes.
Are gas and cost always non-negative? → Yes.
Are the arrays always the same length? → Yes.
Do we need to return all possible starting points? → No, just one valid index or -1.
Is the circuit unidirectional (clockwise only)? → Yes.

2. Identify the Category of the Question

This is a Greedy + Circular Array problem.

It involves:

Simulating travel around a circular route.
Making local decisions to optimize a global outcome.

Common patterns in this category:

Greedy passes through the array
Cumulative sum tracking
Resetting state when a constraint is violated

3. Consider a Brute‑Force Approach to Understand the Problem

The brute-force solution here is to try starting at each station so we can test to see if we can complete the circuit:

Keep track remaining fuel at each step and if at any point fuel goes negative, we can skip to the next station.

Time Complexity: O(n²) since in the worst case, we loop through the whole array for on each iteration

This works, but it's likely not optimal.

4. Brainstorm More Solutions

A great place to start when optimizing on a brute-force solution is to ask yourself the question: is there an opportunity to reduce repeat work?

The reason our brute-force solution is O(n²) is because each time we end up with a failed cycle, we start over from our previous starting point + 1.

So the first question we should ask ourselves is, when we find a cycle that doesn't work, do we really need to start over from our previous starting point + 1?

Or is it possible to skip over the elements that we've already checked, which would allow us to achieve O(n) runtime?

To figure that out, let's look at an example:

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

As we iterate over an array, each visit to a gas station is changing the amount of gas in our tank. We know we have a failed cycle when our tank becomes negative.

In our example, if we start and index 0, we're fine until we hit index 1.

gas            = [1,2,3..]
cost           = [1,1,6..]
tankAfterVisit = [1,2 ...

But we aren't able to continue beyond index 1 because to reach the next gas station requires a tank with 6 gas. Once I get there, my tank would have a "value" of -3.

Ok, so now we know that index 0 is not a valid starting point. That's fine. How do I figure out the best next starting point?

I could start at index 1, but is there any real value in that?

There's not! I already know that passing through that gas station isn't going to be enough to get me to the gas station at index 2. And the same is true for every gas station between my starting point and the point where my gas tank went negative.

That's the key insight! As I'm iterating through my array, if my tank ever goes negative, then I know I need to restart my cycle, and my next best starting point is going to be the gas station after the gas station where my tank went negative.

So to summarize:

Iterate through the gas stations:
- Track the amount of gas in the tank
- If my tank drops below 0 at any station i, that means no valid path can start from start to i.
- So we reset the starting index to i + 1 and reset tank to 0.

And as another optimization, let's remember that if the sum of all costs is greater than the sum of all gas, then a solution is not possible! That small optimization can help us avoid dealing with the circular nature of the array. We know that a solution is possible when sum(gas) > sum(cost), so if we get to the last index of the array without having a solution yet, then that last index must be the valid starting position!

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute Force	O(n²)	O(1)	Easy to understand	Too slow for large n
Greedy (Optimal)	O(n)	O(1)	Fast, elegant, and optimal	Less obvious to derive

6. Write Pseudocode to Structure Your Thoughts

if sum(gas) < sum(cost):
    return -1

start = 0
tank = 0

for i from 0 to n-1:
    tank += gas[i] - cost[i]
    if tank < 0:
        start = i + 1
        tank = 0

return start

7. Consider Edge Cases

Only one station → return 0 if gas[0] >= cost[0], else -1.
All gas == cost → always possible, return 0.
Impossible case → total gas < total cost.
Large arrays (10⁵ elements) → ensure O(n) performance.

8. Write Full Code Syntax (Java)

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int totalCost = 0;
        int tank = 0;
        int start = 0;

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

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

        return totalGas < totalCost ? -1 : start;
    }
}

9. Test Your Code

System.out.println(canCompleteCircuit(new int[]{1,2,3,4,5}, new int[]{3,4,5,1,2})); // 3
System.out.println(canCompleteCircuit(new int[]{2,3,4}, new int[]{3,4,3}));        // -1
System.out.println(canCompleteCircuit(new int[]{5}, new int[]{4}));                // 0
System.out.println(canCompleteCircuit(new int[]{5}, new int[]{5}));                // 0
System.out.println(canCompleteCircuit(new int[]{5}, new int[]{6}));                // -1

10. Key Lessons to Remember for Future Questions

Greedy algorithms often work when problems involve linear choices with local resets.
Circular problems can be flattened with careful use of modular or restarting indices.
Resetting at failure points is a powerful greedy tool. It’s not just about choosing the best at each step but knowing when to reset and start fresh.
Keep space complexity low by only tracking what’s essential. Here we used just three integers.
When looking for ways to optimize, focus on places where you're doing repeat work or calculations.