DFS & Backtracking — Reconstruct Itinerary

Today we are going to be looking at the problem Reconstruct Itinerary.

We always want to start out these problems by making sure we know exactly what is being asked and if there are any constraints. It tells us that our itinerary will always start at JFK and if there are multiple itineraries then we choose the first lexicographically. If we want to construct an itinerary from these separate departures and arrivals then it makes sense to make a map where the key is the departure city and the value is an array that contains the various arrival cities that belong to a departure city.

Once we have our map it is just a matter of connecting our cities. We know that if there are multiple itinerary options that we need the first lexicographically so we will sort each keys arrival array by alphabetical order ensuring we get the correct result.

How do we connect our cities? We can think of our map as a binary tree and we just need to run a dfs function that when it hits our leaf node (the last city in our itinerary) it then adds this city to our result and continues back out of the recursive stack adding each additional city to our itinerary. Since our result array will have the last city first, we simply need to reverse our results array to put ‘JFK’ at the beginning.