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.
I passed all test cases for this problem with an O(N) solution using the following idea: For all partial "trips" starting from 0 and ending at i for 0 < i < N, compute the following information:
1) What is the minimal gas we need to begin the trip at city 0 in order to successfully go from 0 to i?
2) Starting with this minimal amount (assuming the partial trip is even possible) how much gas will we have as we enter city i?
3) During such a trip, what is the largest amount of gas you will ever carry in your tank?
Once you have these three for every 0 < i < N, you also must compute these three for all partial trips starting at some i with 0 < i < N and wrapping around back to zero.
All six of these figures of merit can be computed in O(1) time per city using some slightly clever dynamic programming, and once you have them all for all the cities, it takes O(1) time to check if a city can wrap around completely.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Travel around the world
You are viewing a single comment's thread. Return to all comments →
I think this problem should be labelled as hard. There was a stackoverflow post on this problem about 4 years ago
I passed all test cases for this problem with an O(N) solution using the following idea: For all partial "trips" starting from 0 and ending at i for 0 < i < N, compute the following information:
1) What is the minimal gas we need to begin the trip at city 0 in order to successfully go from 0 to i?
2) Starting with this minimal amount (assuming the partial trip is even possible) how much gas will we have as we enter city i?
3) During such a trip, what is the largest amount of gas you will ever carry in your tank?
Once you have these three for every 0 < i < N, you also must compute these three for all partial trips starting at some i with 0 < i < N and wrapping around back to zero.
All six of these figures of merit can be computed in O(1) time per city using some slightly clever dynamic programming, and once you have them all for all the cities, it takes O(1) time to check if a city can wrap around completely.