The link to the problem: https://leetcode.com/problems/reconstruct-itinerary/
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
Constraints:
- If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary
["JFK", "LGA"]has a smaller lexical order than["JFK", "LGB"]. - All airports are represented by three capital letters (IATA code).
- You may assume all tickets form at least one valid itinerary.
- One must use all the tickets once and only once.
Example
Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]Thoughts:
So what this problem asks us to do is use ALL the flight tickets and use them in a certain order that a person can use to travel from one place to another successfully. The itinerary must begin in “JFK”. It is possible that there is more than one certain order that we can bring a person from “JFK” to different places. We should return the itinerary that has the smallest lexical order.
So the hardest part will be — if we have more than one flight tickets that depart from airport A, how do we choose our next destination? i.e., how do we know the destination we choose is the correct path, but not a dead-end path?
Let’s draw all the airports on the given tickets into a directed graph and let’s see how we can find our best itinerary.
Assume this is our given input: tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]
From the graph, we can clearly see there are 2 tickets for us to fly from our starting point, “JFK”. If we just choose the next airport depends on the alphabetic order, it is possible that we might or we might not reach the “dead-end”. In the above example, the best itinerary is JFK -> NRT -> JFK -> KUL, but how can we get this result using the algorithm?
Idea:
You might think up with an idea to use DFS after we convert them into the directed graph. However, if we use regular DFS to solve the graph, the result will be JFK -> KUL -> NRT. Since in DFS, we will keep touching the nodes until there’s no more path, then we will return back and traverse the next unvisited node.
However, instead of trying to first find our next airport from “JFK”, it will be easier if we keep finding the final airport of our itinerary.
Hence, if we form our itinerary backward, we don’t need to “be afraid” if we see a dead-end. What’s more, we will be happy once we reach a dead-end since that’s mean we found our “final destination”, “second-final destination”, etc.
For example, if we have a more complicated ticket like: [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"],["NRT","ATL"],["ATL","NRT"],["SFO","LAX"],["LAX","SFO"],["KUL","LAX"],["LAX","TPE"]].
We can also get a graph like below —
👷Let’s step by step to see how we can use this strategy to help us get the whole itinerary.
Our goal in each step is to keep using these flying tickets until we can’t fly. The rule of how we choose our next airport is to choose the next airport in alphabetic order.
🔧Step 1. Our first goal is to keep going on the path until we reach our first end. We will go from JFK -> KUL -> LAX -> SFO -> LAX -> TPE. We found that when we reach TPE, we don’t have any flight tickets left flying from TPE. Hence, TPE is our final destination of the whole itinerary.
✈️Current itinerary: [TPE]
🔧Step 2. The previous airport that flies to TPE is LAX. We will then check if we have any tickets left that from LAX to any other airports. Since we can’t fly anywhere from LAX when we already used our LAX-SFO and LAX-TPE tickets, LAX will be our second last destination.
✈️Current itinerary: [LAX->TPE]
Since we know that we have a total of 9 tickets, now we know the 9th ticket we use in this itinerary.
🔧Step 3. The previous airport that flies to LAX is SFO. We will then check if we have any tickets left that from SFO to any other airports. Since we can’t fly anywhere from SFO when we already used our SFO-LAX ticket, SFO will be our “next” last destination.
✈️Current itinerary: [SFO->LAX->TPE]
Now we have found the 8th ticket we use in this itinerary.
🔧Step 4. The previous airport that flies to SFO is LAX. We will then check if we have any tickets left that from LAX to any other airports. Since we can’t fly anywhere from LAX when we already used all the tickets from LAX, LAX will be our “next” last destination.
✈️Current itinerary: [LAX->SFO->LAX->TPE]
Now we have found the 7th ticket we use in this itinerary.
🔧Step 5. The previous airport that flies to LAX is KUL. We will then check if we have any tickets left that from KUL to any other airports. Since we can’t fly anywhere from KUL when we already used the KUL-LAX ticket, KUL will be our “next” last destination.
✈️Current itinerary: [KUL->LAX->SFO->LAX->TPE]
Now we have found the 6th ticket we use in this itinerary.
🔧Step 6. The previous airport that flies to KUL is JFK. We will then check if we have any tickets left that from JFK to any other airports. Yes, we can fly from JFK, so let’s use the unused tickets from JFK. We will fly JFK -> NRT -> ATL -> NRT ->JFK. We found that all other tickets are used from JFK, so we stop at JFK.
✈️Current itinerary: [JFK->KUL->LAX->SFO->LAX->TPE]
Now we have found the 5th ticket we use in this itinerary.
🔧Step 7. The previous airport that flies to JFK is NRT. We will then check if we have any tickets left that from NRT to any other airports. Since we can’t fly anywhere from NRT when we already used the NRT-JFK and NRT-ATL tickets, NRT will be our “next” last destination.
✈️Current itinerary: [NRT->JFK->KUL->LAX->SFO->LAX->TPE]
Now we have found the 4th ticket we use in this itinerary.
🔧Step 8. The previous airport that flies to NRT is ATL. We will then check if we have any tickets left that from ATL to any other airports. Since we can’t fly anywhere from ATL when we already used the ATL-NRT ticket, ATL will be our “next” last destination.
✈️Current itinerary: [ATL->NRT->JFK->KUL->LAX->SFO->LAX->TPE]
Now we have found the 3rd ticket we use in this itinerary.
🔧Step 9. The previous airport that flies to ATL is NRT. We will then check if we have any tickets left that from NRT to any other airports. Since we can’t fly anywhere from NRT when we already used the NRT-JFK and NRT-ATL tickets, NRT will be our “next” last destination.
✈️Current itinerary: [NRT->ATL->NRT->JFK->KUL->LAX->SFO->LAX->TPE]
Now we have found the 2nd ticket we use in this itinerary.
🔧Step 10. The previous airport that flies to NRT is JFK. We will then check if we have any tickets left that from JFK to any other airports. Since we can’t fly anywhere from JFK when we already used the JFK-KUL and JFK-NRT tickets, JFK will be our “next” last destination.
✈️Current itinerary: [JFK->NRT->ATL->NRT->JFK->KUL->LAX->SFO->LAX->TPE]
Now we have found the 1st ticket we use in this itinerary.
👷Done! Now we have finished planning this trip.
Let’s see how we can implement the idea into code. 👇
Code Logic:
The given variable type of the tickets is a List. Hence, our first step in our code is converting the given List into a “directed graph”. Creating a Map will be our best choice. Hence, for each airport name in the map, we will have a List of Strings that are the destinations on the ticket. After creating a map, we will sort all the destination airports in the list in alphabetic order.
After generating our directed graph, we can really start our code.
We will have a helper method to help us to do a depth-first search. We will keep using all the flying tickets until we don’t have any tickets that depart from the current airport. Once we stuck in an airport since we don’t have any ticket left, (i.e., the list in the map is empty), we will add the current airport to our final result list.
⚠️Since we are finding our destination airports backward, we will always add the airport at the first position of the current result list.
Below is the 4ms code that beats 99% —
public List<String> findItinerary(List<List<String>> tickets) {
Map<String, List<String>> map = new HashMap<>();
for(List<String> ticket: tickets)
{
String start = ticket.get(0);
String end = ticket.get(1);
List<String> inner = map.getOrDefault(start, new ArrayList<>());
inner.add(end);
map.put(start,inner);
}
for(String s: map.keySet())
Collections.sort(map.get(s));
List<String> list = new ArrayList<>();
helper(map,list,"JFK");
return list;
}
public void helper(Map<String,List<String>> map, List<String> rst, String cur){
List<String> nexts = map.get(cur);
while(nexts!=null && nexts.size()>0)
{
String next = nexts.get(0);
nexts.remove(0);
helper(map,rst,next);
}
rst.add(0,cur);
}Or we can also use PriorityQueue in the map to make sure all the next airports are stored in alphabetic order and also save a little time for us to call the remove() method of the list. (In Java, the list’s remove method requires O(n) and queue remove only requires O(1).)
public List<String> findItinerary(List<List<String>> tickets) {
Map<String, PriorityQueue<String>> map = new HashMap<>();
for(List<String> ticket: tickets)
{
String start = ticket.get(0);
String end = ticket.get(1);
PriorityQueue<String> inner = map.getOrDefault(start, new PriorityQueue<>());
inner.offer(end);
map.put(start,inner);
}
List<String> list = new ArrayList<>();
helper(map,list,"JFK");
return list;
}
public void helper(Map<String, PriorityQueue<String>> map, List<String> rst, String cur){
PriorityQueue<String> nexts = map.get(cur);
while(nexts!=null && !nexts.isEmpty())
{
String next = nexts.poll();
helper(map,rst,next);
}
rst.add(0,cur);
}
