Skip to content
AI360Xpert
Back to Advanced Graphs
Hard

Reconstruct Itinerary

You are given a list of airline `tickets` where `tickets[i] = [fromi, toi]` represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from `"JFK"`, thus, the itinerary must begin with `"JFK"`. 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"]`. You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Examples

Input:tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output:["JFK","MUC","LHR","SFO","SJC"]
The only valid sequence is JFK -> MUC -> LHR -> SFO -> SJC.
Input:tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output:["JFK","ATL","JFK","SFO","ATL","SFO"]
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

Constraints

  • 1 <= tickets.length <= 300
  • tickets[i].length == 2
  • fromi.length == 3
  • toi.length == 3
  • fromi and toi consist of uppercase English letters.
  • fromi != toi

Hierholzer's Algorithm (Eulerian Path)

Approach

This problem asks us to find an Eulerian path in a directed graph. An Eulerian path visits every edge exactly once. First, we build an adjacency list where each airport points to a list of its destinations, sorted in descending lexical order. We sort in descending order so we can efficiently pop the smallest lexical destination from the end of the list. Starting from "JFK", we use a DFS. In the DFS, as long as the current airport has outgoing flights, we pop the next destination and recursively call DFS on it. When an airport has no more outgoing flights (a dead end), we add it to our itinerary path. Because we add airports to the path when we hit a dead end, the path is built in reverse order. We reverse it at the end to get the correct itinerary.

Complexity Analysis

Time Complexity
O(E log E)
Space Complexity
O(V + E)

Sorting the edges takes O(E log E). The DFS traversal takes O(E) time because we visit each edge exactly once. Space complexity is O(V + E) for the adjacency list and recursion stack.

Solution.java
class Solution {    public List<String> findItinerary(List<List<String>> tickets) {        // Map to store graph: node -> min-heap of destinations        Map<String, PriorityQueue<String>> adj = new HashMap<>();                for (List<String> ticket : tickets) {            adj.putIfAbsent(ticket.get(0), new PriorityQueue<>());            adj.get(ticket.get(0)).offer(ticket.get(1));        }                LinkedList<String> res = new LinkedList<>();        dfs("JFK", adj, res);        return res;    }        private void dfs(String airport, Map<String, PriorityQueue<String>> adj, LinkedList<String> res) {        PriorityQueue<String> destinations = adj.get(airport);                // Visit all destinations in lexical order        while (destinations != null && !destinations.isEmpty()) {            String nextAirport = destinations.poll();            dfs(nextAirport, adj, res);        }                // Add to the front of the list (since we are backtracking)        res.addFirst(airport);    }}