Course4all
Join us on telegram
Home/dsa/Graphs/Reconstruct Itinerary

Reconstruct Itinerary

Master this topic with zero to advance depth.

Reconstruct Itinerary

You are given a list of airline tickets where tickets[i] = [from_i, to_i] 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.

Visual Representation

Tickets: [["MUC","LHR"], ["JFK","MUC"], ["SFO","SJC"], ["LHR","SFO"]] Graph: JFK -> MUC -> LHR -> SFO -> SJC Result: ["JFK", "MUC", "LHR", "SFO", "SJC"]
Hard

Examples

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

Standard path starting from JFK.

Approach 1

Level III: Optimal (Hierholzer's Algorithm)

Intuition

This is finding an Eulerian Path in a directed graph. An Eulerian Path visits every edge exactly once. Hierholzer's algorithm finds this by performing DFS and appending nodes to the result only when they have no more outgoing edges.

Thought Process

  1. Build a graph where each node leads to a PriorityQueue of destinations (to handle lexicographical order requirement).
  2. Start DFS from "JFK".
  3. In DFS:
    • While the current airport has outgoing tickets:
      • Pop the smallest destination and recurse.
    • Add current airport to the head of the result list (or append and reverse at the end).

Pattern: Eulerian Path (Hierholzer)

⏱ O(E \\log E) due to sorting/priority queue.💾 O(V + E) for the graph.

Detailed Dry Run

JFK -> [MUC, SFO], MUC -> [LHR], LHR -> [JFK]

  • DFS(JFK): Pop MUC, DFS(MUC)
    • DFS(MUC): Pop LHR, DFS(LHR)
      • DFS(LHR): Pop JFK... Final order built in reverse: [SFO, JFK, LHR, MUC, JFK]. Reverse it.
java
import java.util.*;

public class Main {
    private Map<String, PriorityQueue<String>> adj = new HashMap<>();
    private LinkedList<String> res = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> t : tickets) {
            adj.computeIfAbsent(t.get(0), x -> new PriorityQueue<>()).add(t.get(1));
        }
        dfs("JFK");
        return res;
    }

    private void dfs(String s) {
        PriorityQueue<String> pq = adj.get(s);
        while (pq != null && !pq.isEmpty()) {
            dfs(pq.poll());
        }
        res.addFirst(s);
    }
}
← Previous QuestionLongest Path in a DAG
Next Question →Shortest Path to Get All Keys