def truckTour(petrolpumps):

petrolRest = [pump[0]-pump[1] for pump in petrolpumps] * 2

for i in range(len(petrolpumps)):

    tank = 0

    for j in range(i, i + len(petrolpumps)):

        tank += petrolRest[j]

        if tank < 0: break     

    if tank < 0: continue

    else: return i

return -1

Python Solution

• def truckTour(petrolpumps):
• fuel=0
• pos=0
• for i in range(len(petrolpumps)):
• fuel+=petrolpumps[i][0]-petrolpumps[i][1]
• if fuel<0:
• fuel=0
• pos=i+1
• return pos

Who and how decides which question is how difficult? This question is definitely easy but it was marked as difficult :D

If you're like me, you're very confused by solutions that only explore the list up to station N-1 after they find a viable starting station at position k, and don't "finish the circle" by checking the road from N-1 back to k. What makes it worse is that most solutions on YouTube just say "it's logical/obvious" and don't explain anything. Let me explain it now that I finally understood.

You have to keep in mind, the problem implicitly states there always exists a solution, since no return value is specified for when a solution doesn't exist. Assume we found a valid starting station at position k. This means that the fuel you will have at position k+1 when starting from k is greater or equal to zero. Ok, let's then assume we are able to reach station N-1. At this point, simple solutions to this problem will return k. Here's why this is a correct solution:

Assume, for this starting station k, that we can't "finish the circle" (i.e. go from N-1 back to the starting station). Ok, then assume that you move up your starting station to k+1 and assume you can also reach the end of the circle. Then, by construction, you won't be able to finish the circle either. This is because when starting at k and moving to k+1, you know you have a positive or zero fuel balance. So if you were unable to finish the circle starting at k, you won't be able to do the trip from N-1 to k either when you start at k+1. Inductively, this implies you can't finish the circle for any station after station k either. Since you're finding the first station that makes the full trip, you also know that any station before k wasn't a valid starting station. So, there would be no solution, which goes against the problem statement.

So, in a convoluted way, reaching the end of the circle from a particular starting station implies you can get from the end back to this starting station.

The logic for understanding why, when you run out of fuel at station i when starting from some previous station k, you can just move your starting station to i+1 is similar. You know the trip from k to k+1 finished with non-negative fuel, so any other trip from stations bigger than k up to i will also necessarily run out of fuel (they will have, at most, the same fuel available as when starting from k).

Hope this helps!

Cpp Solution:

int truckTour(vector<vector<int>> petrolpumps) {
int balance,deficit,start=1;

for(int i =0;i<petrolpumps.size();i++){
    balance += petrolpumps[i][0] - petrolpumps[i][1];

    if(balance < 0){
        deficit += balance;
        start = i+1;
        balance = 0;
    }
}
if(balance + deficit >= 0){
    return start;
}
return -1;
}