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.

- Prepare
- Data Structures
- Queues
- Truck Tour
- Discussions

# Truck Tour

# Truck Tour

#### Sort by

recency

#### |

#### 352 Discussions

#### |

Please Login in order to post a comment

Python

This is one of the easiest hard problems maybe.

A naive solution would be to start a tour from each gas station in turn, and check if the tour is feasible. A feasible tour is one where the fuel in the tank never goes negative while travelling. This is an O(n^2) algorithm.

However, it is easy to see that if a tour starting from S1 and passing through S2, S3, ..., Sk is infeasible, so is a tour from any Sj between S1 and Sk. So you don't need to check those, and the algorithm becomes O(n).

I am not sure queues were needed either -- but that's a cute opportunity to learn from the editorial :)

I'm suprised that the Python brute force approach passed all test cases

def truckTour(petrolpumps):