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;
}

Here is problem solution - HackerRank Truck Tour problem solution in PYthon Java c++ c and javascript

Insanely broken exercise. Terrible test cases where every test has 1000 or more elements making it impossible to learn anything from the failure and it does not actually expect you to do a tour of the circle. In fact, if you try to you will fail. All the successful solutions only go clockwise and don't try to reach all the petrol pumps, they just go to the end of the array. It's shocking that this made it into the 1-week prep course and implies the rest of the HackerRank exercise library is even worse.