This is a solution for leetcode question 134. Gas Station.

Analysis

The target here is to find out if there is a starting point based on the given arrays that could let us go through all these gas stations one by one and back to the starting point in a round. And if it is, return the starting point’s index.

We can solve this question by brutal force. We can try to start at each station and check if we can pass all the stations and back to where we started. The time complexity would be $O(n^2)$ where $n$ is the length of the array.

But that’s pretty slow. So how can we speed it up?

Let’s suppose that we started at station $i$, and we arrive at station $j$ at the moment where,

$$remained\_gas_{i,j} + gas_j < cost_j \tag{1} \label{eq1}$$

The $remained\_gas_{i,j}$ denotes the remained gas when we start from $i$ and arrive at $j$. This means that we are not going to station $j+1$ because we are short of gas, and the starting point would not be $i$.

But how about the stations between $i$ and $j$, are they still possible to be a starting point?

Let’s say we have a station $x$ at somewhere between $i$ and $j$, and when we arrive at $j$ from $x$ we have

$$remained\_gas_{x, j} + gas_j \geq cost_j \tag{2}$$

which means we can go to $j+1$ from $x$. As we know we can arrive at $j$ from $i$, so we definitely can arrive at $x$ from $i$. And it’s obvious that when we arrive at $x$ from $i$, $remained\_gas_{i, x} \geq 0$ otherwise we won’t be able to arrive at $x$. So plus the remained gas from $i$ to $x$, we have

$$remained\_gas_{i,j} + gas_j = remained\_gas_{i,x} + remained\_gas_{x, j} + gas_j \geq cost_j \tag{3} $$

It conflicts with the given condition in $\eqref{eq1}$, so the hypothesis would be false. There will be no station $x$ in between $i$ and $j$ can be a possible starting point. Thus we can skip all the stations in between $i$ and $j$, and use $j+1$ as the new starting point and check if we can arrive at the end from there. The time complexity of this process would be $O(n)$.

We have reduced the time complexity from $O(n^2)$ to $O(n)$, but this only gives a possible starting point, not a definite answer. Because we only computed if we can arrive at the end of the arrays, which is the station $n-1$, but we don’t know if we can go through station $0$ to station $j – 1$ from station $n – 1$ with the remained gas we have.

Supposes the final candidate is station $j$. One possible way to find out if that’s the correct answer is to continue checking if we can arrive at the station $j-1$. And if we can, the answer will be $j$, otherwise, there is no answer to meet the question’s requirements. This process’s time complexity will be $O(j-1)$, and at its worst, it will be $O(n)$, so the total time complexity will be $O(n)$.

Seems like we have a good approach here, but let’s think about this. Is it really needed to go from the beginning and check if we can go through these stations in a second round?

The answer would be no.

When we find the candidate station $j$, we have already checked stations $0$ to $j – 1$, and they are not eligible. Assume that we have changed the starting point for $m$ times, and finally, we chose $j$. So the previous starting points would be a subarray of $0$ to $j-1$, and we can denote all the intervals’ end points as a vector $X$,

$$X = [x_0, x_1, …, x_{m}] \tag{4}$$

$$0 \leq x_k \leq j \tag{5}$$

$$0 \leq k \leq m \tag{6}$$

$$x_0 = 0, x_m = j \tag{7}$$

So at each interval, there is

$$remained\_gas_{x_i, x_{i+1}} \lt 0 \tag{8}$$

$$ 0 \leq i \leq m-1 \tag{9}$$

So if the $remained\_gas_{j, n-1} + \sum_{0 \leq i \leq m-1}{remained\_gas_{x_i,x_{i+1}}} \lt 0$, we can not go back to $j$, therefore there is no possible answer. And these values can be calculated as below.

$$\begin{align}
\sum_{0 \leq i \leq m}{remained\_gas_{x_i,x_{i+1}}} &= \sum_{0 \leq i \leq m-1}{\sum_{x_i \leq k \leq x_{i+1}}{gas_k – cost_k}} \\
&= \sum_{x_0 \leq k \leq x_m}{gas_k – cost_k} \\
&= \sum_{0 \leq k \leq j}{gas_k – cost_k} \\
\end{align} \tag{10} \label{eq2}$$

$$remained\_gas_{j, n-1} = \sum_{j \leq i \leq n-1}{gas_i – cost_i} \tag{11} \label{eq3}$$

So combine $\eqref{eq2}$ and $\eqref{eq3}$,

$$\begin{align}
& remained\_gas_{j, n-1} + \sum_{0 \leq i \leq m-1}{remained\_gas_{x_i,x_{i+1}}} \\ &= \sum_{0 \leq k \leq j}{gas_k – cost_k} + \sum_{j \leq i \leq n-1}{gas_i – cost_i} \\
&= \sum_{0 \leq k \leq n-1}{gas_k – cost_k} \\
\end{align} \tag{12} \label{eq4}$$

Turns out it is just the sum of the value of gas minus cost at each station, and it can be calculated in the first round. By now we have got the final approach, and we can write the code.

Code

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        start = 0
        remained_gas = 0
        total_remained_gas = 0
        for i in range(len(gas)):
            remained_gas += gas[i] - cost[i]
            total_remained_gas += gas[i] - cost[i]
            if remained_gas <= 0:
                remained_gas = 0
                start = i + 1
        if total_remained_gas < 0: return -1
        return start