# algorithms – Gas Station problem proof

I’m trying to prove the solution for the problem Gas Station (LeetCode 134)

Let’s define $$d_i$$ to be the difference $$g_i – c_i$$.

Basically it’s a greedy solution where you look for the first $$k$$ s.t.

$$sum_{i=k}^n d_i ge 0$$

Let’s denote the following:

$$A = sum_{i=1}^k d_i$$

$$B = sum_{i=k+1}^n d_i$$

Notice that by definition of $$k$$, $$A<0$$ and $$Bge 0$$. Since we know that there’s a unique solution

$$A+B ge 0 implies Bge -A$$

We want to show that $$B-A ge 0$$. This will show that we have enough gas for $$A$$ after finishing the $$B$$ part.

So $$B-A ge B+B ge 0$$

Is my proof correct?

Thanks