Reconstruct Itinerary

XXX. Reconstruct Itinerary

Graph

DFS

Sorting

Problem Statement:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in lexical order. You must use all the tickets once and only once.

The starting airport is always "JFK", and the result should follow lexical order when multiple destinations are possible.

Approach:

1. Build a graph where each key (starting airport) maps to a priority queue of destination airports.
2. Perform a Depth First Search (DFS) starting from "JFK".
3. Use a linked list to maintain the order of the itinerary, adding airports to the beginning of the list after all their destinations are visited.
4. Since the priority queue ensures lexical order, this approach guarantees that the itinerary respects the problem's constraints.

Complexity:

Time Complexity: O(E log E), where E is the number of tickets, because of sorting destinations in a priority queue.
Space Complexity: O(V + E), where V is the number of unique airports and E is the number of tickets.

Java Implementation:

public List findItinerary(List> tickets) {
    // Map to store the graph, where each key has a priority queue of destinations.
    Map> map = new HashMap<>();

    // Build the graph from the list of tickets.
    for (List ticket : tickets) {
        map.putIfAbsent(ticket.get(0), new PriorityQueue<>());
        map.putIfAbsent(ticket.get(1), new PriorityQueue<>());
        map.get(ticket.get(0)).offer(ticket.get(1));
    }

    LinkedList path = new LinkedList<>();

    // Start the DFS from "JFK" as the problem usually specifies it as the starting point.
    dfs("JFK", path, map);

    return path;
}

private void dfs(String airport, LinkedList path, Map> map) {
    PriorityQueue pq = map.get(airport);

    // Visit all destinations in lexical order.
    while (pq != null && !pq.isEmpty()) 
        dfs(pq.poll(), path, map);
    

    // Add the airport to the path once all its destinations are visited.
    path.addFirst(airport);
}