Gas Station Problem

In this post,I’d like to share the proof of a property of finite sequences that popped up when I was solving the Gas Station Leetcode problem a while back. It’s one of those statements that feels like it should be true, but you just don’t know until you prove it.

The Original Problem

There are $n$ gas stations arranged along a circular route. The amount of gas you can you can refuel at station $i$ is given by $g_i$, and the amount of gas consumed to drive from station $i$ to station $i+1$ is given by $c_i$ (with $n+1$ understood as looping back to the first station). Your car has an infinite-sized gas tank, but it starts empty. The question is, can you complete the full circuit and, if so, where should you start?

The obvious case is when the gas required to travel the circuit exceeds the amount of available gas, that is, $\sum_{i=1}^n c_i \gt \sum_{i=1}^n g_i$. In this case, you just don’t have enough gas to complete the trip. An interesting question is whether the converse is true: If the total amount of available gas is enough to cover the travel distance, is there always a starting station from which the trip is viable? The answer is yes, and the reason boils down to a property of finite sequences. But first we have to cast the original problem in such a way that the property can be applied.

The Reduction

Let $\delta_i=g_i-c_i$ be the change in fuel after refueling at station $i$ and driving to the next station. If we start at the first station with an empty tank, then our fuel after traveling from station $1$ to station $j$ (not taking the gas at the last station) is given by

For example, $S_{1,2}=\delta_1=g_1-c_1$ is the amount of gas remaining after arriving at the second station, and $S_{1,n+1}=\delta_1+\cdots +\delta_n=(g_1-c_1)+\cdots+(g_n-c_n)$ is the amount of gas remaining after completing the circuit.

Starting from station $1$ is viable precisely when the partial sums $S_{1,2}, S_{1,3}, \ldots, S_{1,n+1}$ remain nonnegative as we go around the circuit. Thus, the gas station problem reduces to finding a rotation of $\delta_1, \delta_2, \ldots, \delta_n$ such that all partial sums are nonnegative.

The Proof

Let $x_1, x_2, \ldots, x_n\in\mathbb{R}$ be a sequence of $n$ real numbers. The claim is that there exists a rotation $x_r, \ldots, x_n, x_1, \ldots, x_{r-1}$ with nonnegative partial sums if and only if the total sum is nonnegative.

One direction is obvious: If all partial sums are nonnegative, then, in particular, the total sum is nonnegative. For the other direction, suppose the sequence has a nonnegative sum ($S_{1,n}=x_1+x_2+\cdots+x_n\geq 0$) and let $S_{1,k}=x_1+x_2+\cdots+x_k$ be a minimal partial sum. We’ll show that the rotated sequence starting after $k+1$ ($x_{k+1}, \ldots, x_n, x_1, \ldots, x_k$) has nonnegative partial sums.

First, we must have $S_{k+1, j}=x_{k+1}+\cdots+x_j\geq0$ for all $k+1\leq j\leq n$ because, otherwise, we’d be able to extend the minimal partial sum $S_{1,k}$ to get a strictly lesser sum, which would contradict our choice of $k$. In other words, we cannot have $S_{k+1,j}<0$ because then we’d have $S_{1,j}=S_{1,k}+S_{k+1,j}<S_{1,k}$. This handles the rotated partial sums up to $x_n$ (before wrapping around). To account for the partial sums that wrap around, note that $S_{1,j}\geq S_{1,k}$ by the minimality of $S_{1,k}$ so that, for all $1\leq j\leq k$, we have

In conclusion, a finite sequence of real numbers can be rotated such that all of its partial sums are nonnegative if and only if its total sum is nonnegative, and, in particular, this is achieved by the rotation starting after a minimum partial sum in the original sequence.

The Solution

With this, we can solve the gas station problem by checking whether the total sum is nonnegative and looking for the position of the minimal partial sum:

def canCompleteCircuit(gas, cost):
        n = len(gas)

        delta_ps = gas[0]-cost[0]  # delta partial sum
        min_ps = delta_ps          # min partial sum
        k = 0                      # index of min partial sum
        for i in range(1,n):
            delta_ps += gas[i]-cost[i]
            if delta_ps < min_ps:
                min_ps = delta_ps
                k = i

        if delta_ps < 0:
            return -1     # negative total sum; no solution
        return (k+1) % n  # start after minimal partial sum

---

Resources

• “134. Gas Station.” Leetcode, leetcode.com/problems/gas-station/. Accessed 1 Mar. 2026.
• “Reductio Ad Absurdum.” Wikipedia, 22 July 2020, en.wikipedia.org/wiki/Reductio_ad_absurdum. Accessed 1 Mar. 2026.