Problem Statement

You are given a list of airline tickets represented by pairs of departure and arrival airports [from, to].
Reconstruct the itinerary in order.
All tickets belong to a man who departs from "JFK". Thus, the itinerary must begin with "JFK".

If there are multiple valid itineraries, return the one with 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 must use all the tickets exactly once.

---

Example 1

Input:

tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Output:

["JFK","MUC","LHR","SFO","SJC"]

---

Example 2

Input:

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Output:

["JFK","ATL","JFK","SFO","ATL","SFO"]

Explanation:
Both itineraries are valid, but
["JFK","ATL","JFK","SFO","ATL","SFO"] is lexicographically smaller than
["JFK","SFO","ATL","JFK","ATL","SFO"].

---

Constraints

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• Each airport is represented by a string of length 3 (uppercase English letters).
• You must use all tickets exactly once.

---

Approach

This problem is a graph traversal challenge.
We can model each ticket as a directed edge from one airport to another.
The task is to find a path that uses every edge exactly once — this is a form of Eulerian Path problem.

However, there’s one additional requirement — the result must be lexicographically smallest.
So we need to always pick the smallest possible next airport.

We will use Hierholzer’s algorithm (commonly used to find Eulerian paths), along with a min-heap (PriorityQueue) to maintain lexical order.

---

Step-by-Step Algorithm

1. Build a graph:
   • Use a Map<String, PriorityQueue<String>> to represent the adjacency list.
   • For each ticket [from, to], add to to the priority queue of from.
2. Traverse the graph:
   • Start from "JFK".
   • Perform Depth-First Search (DFS).
   • For the current airport:
     • While it has destinations left, recursively call DFS for the next smallest destination.
   • Once you reach an airport with no outgoing edges, add it to the itinerary list.
3. Reverse the result:
   • The itinerary will be built in reverse order (post-order traversal), so reverse it at the end.

---

Java Implementation

import java.util.*;

public class ReconstructItinerary {

    public List<String> findItinerary(List<List<String>> tickets) {
        // Step 1: Build graph using PriorityQueue for lexical order
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for (List<String> ticket : tickets) {
            graph.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>()).add(ticket.get(1));
        }

        // Step 2: Perform DFS starting from JFK
        List<String> itinerary = new LinkedList<>();
        dfs("JFK", graph, itinerary);

        // Step 3: Itinerary is built in reverse order
        return itinerary;
    }

    private void dfs(String airport, Map<String, PriorityQueue<String>> graph, List<String> itinerary) {
        PriorityQueue<String> destinations = graph.get(airport);
        while (destinations != null && !destinations.isEmpty()) {
            dfs(destinations.poll(), graph, itinerary);
        }
        // Add airport to the front (LinkedList allows O(1) insertion at head)
        itinerary.add(0, airport);
    }

    public static void main(String[] args) {
        ReconstructItinerary solver = new ReconstructItinerary();
        
        List<List<String>> tickets1 = Arrays.asList(
            Arrays.asList("MUC","LHR"),
            Arrays.asList("JFK","MUC"),
            Arrays.asList("SFO","SJC"),
            Arrays.asList("LHR","SFO")
        );
        System.out.println(solver.findItinerary(tickets1));

        List<List<String>> tickets2 = Arrays.asList(
            Arrays.asList("JFK","SFO"),
            Arrays.asList("JFK","ATL"),
            Arrays.asList("SFO","ATL"),
            Arrays.asList("ATL","JFK"),
            Arrays.asList("ATL","SFO")
        );
        System.out.println(solver.findItinerary(tickets2));
    }
}

---

Explanation

• Graph building ensures that from every airport, we can access its destinations in sorted order.
• DFS traversal ensures we use every ticket exactly once.
• When recursion finishes from a node, that means we have explored all flights from that airport, so we add it to the front of the itinerary.
• The final list represents the correct travel order.

---

Time Complexity

• Building the graph: O(E log E) because each insertion in a priority queue takes O(log E) (where E is number of edges).
• DFS traversal: O(E) since every edge is visited once.
• Overall: O(E log E)

Space Complexity

• Graph + recursion stack: O(V + E)

---

Key Takeaways

• The problem models an Eulerian path with lexical ordering.
• Using a PriorityQueue ensures lexicographically smallest order.
• Hierholzer’s algorithm provides an efficient solution to cover all edges exactly once.