Reconstruct Itinerary

Good question to ask interviewers on such problems:

• Can there be duplicate trips (i.e. two identical directed edges). In the case of this problem, yes there can be

Basically, do the DFS from start until the number of trips we have done equals the total number of tickets i.e. trips

To ensure we go in the required order, we sort the destinations in the adjacency list for each source

Basically just do a brute-force Depth-first Search

We should return at the first solution found, and to make sure that we don't recur unnecessarily, we sort the destination list (from the adjacency list) so that the first valid path we find is lexicographically the best solution

• i.e. if there's two tickets ['JFK', 'ATL'] and ['JFK', 'SFO'], our key in the adjacency list should be 'JFK': ['ATL', 'SFO'] instead of 'JFK': ['SFO', 'ATL'].
  • We first create the adjacency list using a set to avoid duplicate trips (the duplicates will be accounted for using the visits_left hashmap)
  • Then we turn it back to a sorted list since a set does not maintain order in Python

Since there can be multiple duplicate itineraries, instead of a visited set, we use a hashmap to keep track of how many more trips we have left.

• Similar to a set, but instead of nodes we keep track of edges i.e. trips
• For example, if we have two trips in our graph going from JFK -> SFO, our hashmap would have the key value pair of {'JFK-SFO': 2}
  • Only when the value here is 0, means we can no longer take the same trip. This is akin to the edge/trip already being visited

NeetCode uses a list so that there can be multiple destinations, and he inserts and removes them. Personally I don't like this solution so I didn't go with it.