We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Truck Tour
You are viewing a single comment's thread. Return to all comments →
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!