Back to DSA
Reconstruct Itinerary
hardGiven a collection of flight tickets, each specifying a departure and arrival airport, construct the travel itinerary that uses every ticket exactly once, beginning from 'JFK'. If more than one valid itinerary exists, return the one that is lexicographically smallest.
Examples
Example 1:
Input:
tickets = [["JFK","BOS"],["BOS","SFO"],["SFO","JFK"],["JFK","LAX"]]Output:
["JFK","BOS","SFO","JFK","LAX"]Explanation: All tickets are used in this route, and it is the lexicographically smallest option.
Example 2:
Input:
tickets = [["JFK","ATL"],["ATL","JFK"]]Output:
["JFK","ATL","JFK"]Explanation: The only route uses both tickets.
Hints
import java.util.*;
class Solution {
public List<String> findItinerary(List<List<String>> tickets) {
Map<String, PriorityQueue<String>> graph = new HashMap<>();
for (List<String> t : tickets) {
graph.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).add(t.get(1));
}
LinkedList<String> result = new LinkedList<>();
dfs("JFK", graph, result);
return result;
}
private void dfs(String node, Map<String, PriorityQueue<String>> graph, LinkedList<String> result) {
PriorityQueue<String> neighbors = graph.get(node);
while (neighbors != null && !neighbors.isEmpty()) {
dfs(neighbors.poll(), graph, result);
}
result.addFirst(node);
}
}Time complexity
O(E log E)Space complexity
O(V + E)