Solving Gas Station Circuit Problem with Greedy Approach

Introduction and Core Concepts

The gas station circuit problem is a classic greedy algorithm challenge that appears frequently in coding interviews, competitive programming, and real-world route optimization. At its core, the problem asks a deceptively simple question: given a circular route with multiple gas stations, each providing a certain amount of fuel and requiring a certain cost to travel to the next station, can you complete a full circuit? And if so, where should you start?

Formally, you are given two integer arrays, gas and cost, both of length n. The array gas[i] represents the amount of gas available at station i, while cost[i] represents the gas required to travel from station i to station (i + 1) % n. You start with an empty tank at one station. The goal is to find the smallest index of a starting station from which you can travel around the entire circle once in the clockwise direction without running out of gas. If no such starting point exists, you must return -1.

Why does this problem matter beyond interviews? The gas station circuit is a canonical example of a greedy choice property in action. It teaches a fundamental lesson: sometimes a global feasibility question (can we complete the whole circle?) can be answered with a single linear scan and O(1) extra space, without trying every possibility. The problem also introduces the powerful concept of prefix sums, net gain, and circular array handling — techniques that generalize to load balancing, resource allocation, and circular scheduling problems. Understanding this problem deeply builds intuition for when a greedy strategy is provably optimal and when it is not.

Key Definitions and Assumptions

To reason correctly about the problem, we define net[i] = gas[i] - cost[i] as the net fuel gain (or loss) at station i. If net[i] is positive, you leave the station with more fuel than you arrived with; if negative, you lose fuel on the leg to the next station. The total net fuel for the entire circuit is total = sum(net[i]) for all i. A necessary and sufficient condition for a solution to exist is that total >= 0. If the total gas is less than the total cost, no starting point can succeed, regardless of strategy.

We also assume that the car has an unlimited tank capacity, that fuel consumption is deterministic, and that you must visit stations in order. You cannot skip stations or refuel partially — you collect all gas at a station when you arrive. These assumptions simplify the model but are realistic for many abstract resource-circulation problems.

Finally, the problem guarantees uniqueness in its most common formulation: if a solution exists, it is unique. This property is crucial for the greedy algorithm's correctness and simplifies the return value to a single index. When multiple solutions are possible in variations, the algorithm can be extended to enumerate all valid starting points.

How It Works

The naive way to solve the gas station problem is brute force: try every station as a starting point and simulate the entire trip, which takes O(n²) time. The greedy insight eliminates this inefficiency by observing two facts. First, as noted, if the total gas is insufficient, we can immediately return -1 without any simulation. Second, if we run out of gas while traveling from a candidate start s to station k, then no station between s and k can be a valid starting point either.

Why is the second fact true? Suppose you start at s with 0 fuel and your tank becomes negative upon arriving at k. This means the cumulative sum net[s] + net[s+1] + ... + net[k] is negative. For any intermediate station j where s < j <= k, the cumulative sum from j to k must also be negative, because the sum from s to j-1 was non-negative up to the point of failure (otherwise you would have failed earlier). Therefore, starting at j cannot succeed in reaching k+1, let alone completing the full circle. This allows us to greedily jump the candidate start to k+1.

The algorithm therefore maintains two variables in a single pass: total_tank to track the overall feasibility and curr_tank to track the fuel balance of the current candidate segment. It also maintains start, the current candidate starting index. As we iterate from i = 0 to n-1, we add net[i] to both tanks. If curr_tank becomes negative, we know the current start is invalid, so we reset start = i + 1 and reset curr_tank = 0. At the end, if total_tank >= 0, the start we found is the answer; otherwise, no solution exists.

The Greedy Choice Property

This algorithm is greedy because it makes an irrevocable local decision: once a segment fails, it is discarded forever. It never backtracks. The correctness proof relies on the argument above — the discarded segment can never contain a valid start. This is the hallmark of a greedy algorithm: a locally optimal choice (abandon a failing segment) leads to a globally optimal solution (find the unique feasible start if it exists).

Another way to visualize the algorithm is through prefix sums on a doubled array. If you duplicate the net array to handle circularity and compute prefix sums, the valid start is the position of the minimum prefix sum. The greedy scan implicitly finds this minimum without explicitly constructing the doubled array, which is why it achieves O(1) space.

Circular Handling Without Extra Space

A common point of confusion is how a single linear pass can handle a circular route. The trick is that we do not need to simulate wrapping around. By tracking total_tank, we verify global feasibility. By tracking curr_tank and resetting the start, we identify the point after the worst deficit. If total fuel is sufficient, the tank accumulated from that optimal start will be enough to cover the initial deficit that caused earlier failures, effectively bridging the circular gap.

Implementation

Implementing the greedy solution in Python is concise and elegant. The key is to correctly manage the two tank variables and the start pointer. Below are multiple implementations that illustrate the core logic, a brute-force baseline for comparison, and extensions for more complex requirements.

The canonical implementation runs in O(n) time and O(1) space. It handles edge cases such as empty arrays, single stations, and large inputs efficiently. Pay close attention to the reset condition: we only reset when curr_tank < 0, not when it is zero, because zero fuel is still sufficient to continue (you have not yet failed).

def can_complete_circuit(gas, cost):
    """
    Greedy O(n) solution for Gas Station Circuit Problem.
    Returns starting index if circuit can be completed, else -1.
    """
    n = len(gas)
    if n == 0:
        return -1
    
    total_tank = 0  # Overall gas balance for feasibility check
    curr_tank = 0   # Current segment balance
    start = 0       # Candidate starting station

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

        # If we cannot reach station i+1 from current start,
        # no station between start and i can be valid.
        if curr_tank < 0:
            start = i + 1
            curr_tank = 0

    # If total gas >= total cost, start is valid; else no solution
    return start if total_tank >= 0 and start < n else -1

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

def can_complete_circuit_bruteforce(gas, cost):
    """
    Brute-force O(n^2) solution for comparison and verification.
    Tries every starting station and simulates the full circuit.
    Useful for testing greedy correctness on small inputs.
    """
    n = len(gas)
    if n == 0:
        return -1

    for start in range(n):
        tank = 0
        valid = True
        for i in range(n):
            idx = (start + i) % n
            tank += gas[idx] - cost[idx]
            if tank < 0:
                valid = False
                break
        if valid:
            return start
    return -1

# This version is correct but too slow for large n (e.g., n = 10^5)

def find_all_valid_starts(gas, cost):
    """
    Variation: Find ALL valid starting stations (if multiple exist).
    This handles the case where uniqueness is not guaranteed.
    Uses prefix sums on doubled array concept.
    Time: O(n), Space: O(n)
    """
    n = len(gas)
    if n == 0:
        return []

    net = [gas[i] - cost[i] for i in range(n)]
    if sum(net) < 0:
        return []

    # Build prefix sum of doubled net array
    # prefix[0] = 0, prefix[i+1] = prefix[i] + net[i % n]
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]

    # Use deque to find minimum prefix in sliding window of size n
    # A start s is valid if min(prefix[s+1 .. s+n]) - prefix[s] >= 0
    from collections import deque
    dq = deque()
    valid_starts = []

    # Initialize deque for first window [1, n]
    for i in range(1, n+1):
        while dq and prefix[dq[-1]] >= prefix[i]:
            dq.pop()
        dq.append(i)

    for s in range(n):
        # Check if s is valid
        min_in_window = prefix[dq[0]]
        if min_in_window - prefix[s] >= 0:
            valid_starts.append(s)

        # Slide window: remove s+1, add s+n+1
        if dq[0] == s + 1:
            dq.popleft()
        nxt = s + n + 1
        if nxt <= 2 * n:
            while dq and prefix[dq[-1]] >= prefix[nxt]:
                dq.pop()
            dq.append(nxt)

    return valid_starts

# Example: gas = [2,2,2], cost = [2,2,2] -> all stations valid
print(find_all_valid_starts([2,2,2], [2,2,2]))  # [0, 1, 2]

class GasStationSolver:
    """
    Object-oriented implementation with detailed simulation and
    path tracking for debugging and visualization.
    """
    def __init__(self, gas, cost):
        self.gas = gas
        self.cost = cost
        self.n = len(gas)
        self.net = [g - c for g, c in zip(gas, cost)]

    def solve_greedy(self):
        total = 0
        curr = 0
        start = 0
        for i in range(self.n):
            total += self.net[i]
            curr += self.net[i]
            if curr < 0:
                # Debug: print failure segment
                # print(f"Failed from {start} to {i}, resetting to {i+1}")
                start = i + 1
                curr = 0
        return start if total >= 0 else -1

    def simulate_from(self, start):
        """Simulate trip from start, return tank levels at each station."""
        if start < 0 or start >= self.n:
            return None
        tank = 0
        levels = []
        for i in range(self.n):
            idx = (start + i) % self.n
            tank += self.net[idx]
            levels.append(tank)
            if tank < 0:
                return levels  # Failed early
        return levels

solver = GasStationSolver([5, 1, 2, 3, 4], [4, 4, 1, 5, 1])
start = solver.solve_greedy()
print(f"Optimal start: {start}")  # Output: 4
print(f"Tank levels: {solver.simulate_from(start)}")

Step-by-Step Example

Let's walk through a concrete example to make the greedy logic tangible. Consider gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2]. This gives net = [-2, -2, -2, 3, 3]. The total net is -2 -2 -2 +3 +3 = 0, so a solution exists. We will trace the greedy algorithm step by step.

We initialize total_tank = 0, curr_tank = 0, and start = 0. Iteration 0: net[0] = -2. Both tanks become -2. Since curr_tank < 0, we reset start = 1 and curr_tank = 0. This means starting at station 0 fails immediately — you need 3 gas to leave but only have 1. No surprise.

Iteration 1: net[1] = -2. total_tank = -4, curr_tank = -2. Again curr_tank < 0, so start = 2, curr_tank = 0. Starting at station 1 also fails. Iteration 2: net[2] = -2. total_tank = -6, curr_tank = -2. Reset to start = 3, curr_tank = 0. Stations 0, 1, and 2 are all eliminated as candidates.

Iteration 3: net[3] = 3. total_tank = -3, curr_tank = 3. Since curr_tank >= 0, we do not reset. start remains 3. Iteration 4: net[4] = 3. total_tank = 0, curr_tank = 6. Loop ends. Since total_tank >= 0, we return start = 3. Let's verify by simulating from station 3: Start with 0, collect 4 gas, pay 1 to go to station 4 (tank = 3). At station 4, collect 5 (tank = 8), pay 2 to go to station 0 (tank = 6). At station 0, collect 1 (tank = 7), pay 3 to go to station 1 (tank = 4). At station 1, collect 2 (tank = 6), pay 4 to go to station 2 (tank = 2). At station 2, collect 3 (tank = 5), pay 5 to return to station 3 (tank = 0). We never went negative, so station 3 is valid.

Visualizing Tank Levels

Another helpful visualization is to plot cumulative net sums. If you start at 0, the cumulative sums are [-2, -4, -6, -3, 0]. The minimum is -6 at index 2. The optimal start is always the index after the minimum prefix sum — in this case, 3. This aligns perfectly with our greedy result and provides an alternative O(n) method using prefix minima.

Consider a failing case: gas = [2, 3, 4], cost = [3, 4, 3], so net = [-1, -1, 1] and total = -1. The greedy scan would proceed: start=0 fails at i=0 (curr=-1 → start=1), start=1 fails at i=1 (curr=-1 → start=2), start=2 succeeds for its segment (curr=1), but at the end total_tank = -1 < 0, so we return -1. No start can overcome the global deficit.

Complexity Analysis

Complexity analysis is where the greedy approach truly shines compared to brute force. The performance gap becomes enormous as n grows, which is why interviewers expect the optimal solution.

The greedy algorithm performs a single pass over the arrays, doing O(1) work per element. It uses only three scalar variables (total_tank, curr_tank, start) regardless of input size. This makes it optimal in both time and space for this problem.

Brute force, by contrast, tries each of the n starting points and for each simulates up to n steps, leading to quadratic time. It also uses O(1) extra space but is impractical for large inputs (e.g., n = 10^5 would require 10 billion operations). The prefix-sum with deque variation for finding all valid starts trades some space for the ability to enumerate multiple solutions.

Note that for the greedy single pass, best, average, and worst cases are all O(n) because we must always scan the entire array once to compute total_tank and verify feasibility, even if we find the start early. There is no early exit for the total check, though some implementations combine the two checks and can exit early if total_tank is already known to be negative and no start can succeed — but strictly speaking, we need the full sum.

Space complexity is a key differentiator. The O(1) greedy solution is ideal for embedded systems or streaming contexts where memory is constrained. The O(n) variations are only needed when you must return all valid stations or reconstruct the full tank-level history.

Scalability Considerations

For n up to 10^6, the greedy solution runs in milliseconds in Python, while brute force would time out. For n up to 10^5, which is common on LeetCode (Problem 134), the greedy solution easily passes. If gas and cost values are large (up to 10^9), Python's arbitrary-precision integers handle it, but in languages like Java or C++ you must use 64-bit integers to avoid overflow when summing.

Variations and Optimizations

The basic gas station problem has several interesting variations that test deeper understanding. One common variation asks for all valid starting points instead of just one. Another introduces a maximum tank capacity, which breaks the simple total-sum feasibility condition and requires a more careful simulation. A third variation allows refueling at most once or limits the number of stops.

An optimization for the standard problem is to avoid recomputing gas[i] - cost[i] multiple times by precomputing the net array. However, this uses O(n) extra space, so the most space-efficient version computes the difference on the fly. Another micro-optimization is to use local variables for array access in Python loops to reduce attribute lookup overhead, though this rarely matters in interviews.

A more advanced variation is the circular gas station with capacity constraint C. Here, you cannot carry more than C fuel, so even if total gas is sufficient, you might waste fuel by overfilling. The greedy reset logic still applies, but you must cap curr_tank at C after each refuel. This changes the problem from O(n) to potentially requiring a deque or segment tree for efficient range minima, and the uniqueness guarantee no longer holds.

Handling Multiple Test Cases

In competitive programming, you may need to answer many queries on the same gas/cost arrays with updates. For dynamic versions where gas or cost values change, a segment tree storing total sum and minimum prefix sum can answer feasibility and find the optimal start in O(log n) per update and query. This is a significant optimization when q, the number of queries, is large.

Another variation is the non-circular version: find the starting point to travel from station 0 to station n-1 (a linear route) without running out. This is simpler — you just need to check if any prefix sum goes negative. The circular nature is what makes the original problem non-trivial.

Real-World Applications

While the gas station metaphor is concrete, the underlying abstraction — a circular resource circulation with net gains and losses — appears in many real systems. Recognizing this pattern allows you to apply the same greedy insight far beyond fuel stations.

In operating systems and networking, the problem models token ring networks and circular buffer management. A token or data packet circulates through nodes, each node may add or consume resources (bandwidth, energy, processing credits). Determining if a circulation can complete without starvation is exactly the gas station problem. Similarly, in round-robin CPU scheduling with energy-aware cores, each task may harvest energy (e.g., from solar) and consume energy to execute; the scheduler must find a starting task order that avoids energy depletion.

In logistics and supply chain, delivery trucks on a circular route pick up and deliver goods. The gas station logic determines if a truck can complete its route without overloading or running empty, and where to start to minimize maximum load. Electric vehicle (EV) routing with charging stations is a direct analogue, especially when battery capacity is large enough to be considered unlimited for the route length.

In finance, the problem appears as cash flow analysis for a cyclical business. Each month has revenue (gas) and expenses (cost). The question is whether the business can survive a full year without borrowing, and which month to start the fiscal year to minimize required initial capital. The minimum prefix sum corresponds to the maximum cash shortfall that must be covered.

Systems and Infrastructure Examples

Web servers and databases use circular log buffers and write-ahead logs that wrap around. Ensuring that a writer can complete a full cycle without overwriting unflushed data involves similar prefix-sum checks. In distributed systems, consistent hashing rings assign data to nodes circularly; rebalancing after node failures can be modeled as finding a valid start for data migration without overloading any node.

Even in game design, circular board games (like Monopoly) where players collect and pay money at each square can use this logic to determine if a player can complete a lap without bankruptcy, which is useful for AI difficulty balancing.

Comparison with Alternatives

Understanding how the greedy approach compares to other algorithmic strategies helps you choose the right tool and explain trade-offs in interviews. The gas station problem can be solved by brute force, greedy, dynamic programming, or prefix-sum methods, but not all are equally efficient or appropriate.

Brute force is the most intuitive but scales poorly. It is useful as a reference implementation for testing but should never be submitted as the final solution for large inputs. Dynamic programming is overkill here — there is no overlapping subproblem structure that DP would exploit, and a DP solution would be more complex without improving complexity. Divide and conquer could be applied but offers no advantage over the linear greedy scan.

The prefix-sum method is essentially equivalent to the greedy method in terms of asymptotic complexity but provides more insight and can be extended to find all valid starts. It explicitly computes cumulative sums and finds the minimum, which is conceptually clear but uses extra space if you store the full prefix array. The greedy method is an optimized, space-efficient version of the same idea.

Another alternative is to use a queue or simulation with backtracking, where you try a start and if it fails, you backtrack and try the next. This is similar to brute force but can be slightly optimized with memoization of failed segments, yet it still degrades to O(n²) in the worst case and is harder to prove correct.

In summary, the greedy single pass is the gold standard for the standard problem due to its optimal time and space. Use prefix sums when you need to explain the intuition or extend to all-starts. Avoid brute force and DP except for verification or when constraints are tiny.

Common Mistakes and Best Practices

Even though the algorithm is short, there are several pitfalls that cause incorrect submissions. Being aware of these will save debugging time and impress interviewers with your attention to detail.

A frequent mistake is forgetting the total feasibility check. Some candidates correctly find a candidate start via the curr_tank reset logic but forget to verify total_tank >= 0 at the end, returning a false positive when no solution exists. Always remember that the greedy scan finds the best candidate, but only the total sum tells you if that candidate actually works.

Another common error is resetting curr_tank incorrectly. After a failure at i, you must set curr_tank = 0, not carry over the negative value. Carrying the negative deficit would incorrectly penalize the next segment. Similarly, the new start should be i + 1, not i. Off-by-one errors here lead to infinite loops or missed solutions.

Handling edge cases is also critical. Test with n = 1: if gas[0] >= cost[0], the answer is 0, else -1. Test with all equal values: all stations should be valid in the all-starts variation, but the single-start version should return 0. Test with large values to ensure no integer overflow in other languages. And test with start == n at the end — if the last station causes a reset, start becomes n, which is out of bounds and should be treated as -1 unless total is sufficient (which it won't be in that case).

Best Practices for Clean Code

Write self-documenting code: use names like total_tank and curr_tank instead of a and b. Add comments explaining the greedy invariant. Validate inputs at the start (check for mismatched array lengths, empty arrays). Use Python's zip for clean iteration when precomputing net, but compute on the fly for O(1) space.

For interviews, start by stating the two key insights (total check and skipping failed segments) before coding. Walk through a small example to demonstrate understanding. Then code the greedy solution and mention the brute-force baseline for contrast. Finally, discuss complexity and edge cases without being prompted — this shows thoroughness.

• Always check total_tank >= 0 before returning start.
• Reset curr_tank = 0 and start = i + 1 on failure; do not carry deficit.
• Handle n == 0 and n == 1 explicitly.
• Escape circularity correctly — do not actually double the array unless needed for all-starts.
• Test with both feasible and infeasible examples, and verify by simulation.
• Use 64-bit integers in Java/C++ to avoid overflow on sum.

Interview Questions

Interviewers love the gas station problem because it tests greedy reasoning, circular array handling, and proof skills. Here are common questions and how to approach them.

Q1: Why does skipping stations between start and failure point work? Prove it.

Answer: Suppose we start at s and fail at k (so sum(s..k) < 0) and for any j in (s..k], we claim j cannot be valid. Proof by contradiction: assume j is valid, so the circuit from j can complete. Since we reached k from s with non-negative tank until k, the sum s..j-1 is >= 0. Then sum(j..k) = sum(s..k) - sum(s..j-1) < 0 - (non-negative) < 0, so starting at j would also fail at k, contradicting validity. This is the core greedy choice proof.

Q2: What if the car has a finite tank capacity C? Does the greedy algorithm still work?

Answer: No, the simple total-sum check fails with finite capacity because excess fuel is wasted when the tank is full. You cannot just sum net gains; you must simulate with capping: tank = min(C, tank + gas[i]) - cost[i]. The skipping optimization still holds (failed segment cannot contain a valid start), but you must simulate each candidate segment with capping, and the overall feasibility is not determined by total sum alone. The problem becomes more complex and may require O(n) per candidate or a more advanced data structure.

Q3: How would you find all valid starting stations efficiently?

Answer: Use prefix sums on a doubled array and a sliding window minimum. Compute prefix for 2n elements, then for each s in 0..n-1, check if min(prefix[s+1 .. s+n]) - prefix[s] >= 0. A deque maintains the minimum in O(1) amortized per window slide, yielding O(n) time and O(n) space. This is optimal for enumerating all solutions.

Q4: Can you solve it without explicitly checking total gas vs total cost?

Answer: Yes, implicitly. The greedy algorithm's final start is valid if and only if total >= 0. If you track total_tank separately, you need the check. Alternatively, after finding start, you could simulate one full circuit from start to verify — this is O(n) extra work but avoids a separate total variable. However, maintaining total_tank during the same pass is more efficient and is the standard approach.

Q5: What is the time complexity if you are given the net array directly instead of gas and cost?

Answer: Still O(n) time and O(1) space. The input size is still n, and the algorithm only needs net values. In fact, this is slightly simpler as you avoid the subtraction. The complexity does not change — you still need one pass to find the start and verify total non-negativity. If you only need to find the start and are guaranteed total >= 0, you could even do it in one pass without storing total, but the problem usually requires the feasibility check.

Preparing answers to these questions, along with a clean implementation and a step-by-step trace, will demonstrate mastery of greedy algorithms and circular reasoning — skills that transfer to many other problems like jump game, candy distribution, and task scheduling.