332. Reconstruct Itinerary

This problem asks to reconstruct a flight itinerary given a list of tickets, where each ticket represents a flight from one airport to another. The itinerary must start at "JFK" and use all tickets exactly once. If multiple valid itineraries exist, the lexicographically smallest one should be returned.

Approach: Depth-First Search (DFS) with Hierholzer's Algorithm

This problem can be efficiently solved using a Depth-First Search (DFS) algorithm, incorporating aspects of Hierholzer's algorithm for finding Eulerian paths in a directed graph.

1. Graph Representation: We represent the flight data as a directed graph. Each airport is a node, and a ticket [from, to] represents a directed edge from from to to.

2. Sorting Tickets: Crucially, we sort the tickets in reverse lexicographical order based on the destination airport (to). This ensures that when we explore paths from an airport, we prioritize lexicographically smaller destinations first. This is key to obtaining the lexicographically smallest itinerary.

3. DFS Traversal: We perform a depth-first search starting from "JFK". The DFS function recursively explores outgoing edges (flights) from the current airport. It continues until it reaches an airport with no more outgoing edges. At that point, it adds the airport to the itinerary (in reverse order).

4. Building the Itinerary: As the DFS backtracks, it appends the visited airports to the itinerary. Because we add airports to the itinerary during backtracking, we reverse the itinerary at the end to get the correct order.

5. Handling Multiple Edges: The graph might have multiple edges between airports (multiple flights between the same two airports). The sorting ensures that we process the lexicographically smaller destination first, preventing deadlocks and finding the correct path.

Time and Space Complexity

• Time Complexity: O(E log E), where E is the number of edges (tickets). The sorting of tickets dominates the time complexity. The DFS traversal takes linear time relative to the number of edges.

• Space Complexity: O(E + V), where E is the number of edges and V is the number of vertices (airports). This is to store the graph (adjacency list) and the itinerary.

Code Implementation (Python)

from collections import defaultdict
 
class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        for start, end in sorted(tickets, reverse=True):  # Reverse lexicographical sort
            graph[start].append(end)
 
        result = []
        def dfs(airport):
            while graph[airport]:
                dfs(graph[airport].pop())
            result.append(airport)
 
        dfs("JFK")
        return result[::-1]  # Reverse the result to get the correct itinerary order
 

Code Implementation (Java)

import java.util.*;
 
class Solution {
    private Map<String, List<String>> graph = new HashMap<>();
    private List<String> result = new ArrayList<>();
 
    public List<String> findItinerary(List<List<String>> tickets) {
        // Sort tickets in reverse lexicographical order by destination
        Collections.sort(tickets, (a, b) -> b.get(1).compareTo(a.get(1)));
 
        for (List<String> ticket : tickets) {
            graph.computeIfAbsent(ticket.get(0), k -> new ArrayList<>()).add(ticket.get(1));
        }
 
        dfs("JFK");
        Collections.reverse(result); //Reverse to get correct order
        return result;
    }
 
    private void dfs(String airport) {
        while (graph.containsKey(airport) && !graph.get(airport).isEmpty()) {
            String nextAirport = graph.get(airport).remove(graph.get(airport).size() - 1);
            dfs(nextAirport);
        }
        result.add(airport);
    }
}

Other languages (C++, Go, TypeScript) would follow a very similar structure, mainly differing in syntax and data structure implementations. The core logic remains the same: sorting tickets, building a graph, and performing a depth-first search with backtracking to construct the lexicographically smallest itinerary.