Problem Statement

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 exactly once.

Additional information

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

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: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

Brute Force (DFS with Backtracking)

Intuition

We need to visit every single ticket (edge) exactly once. This is a classic graph traversal problem. Since we need the lexicographically smallest path, we can sort our tickets first.

Starting from "JFK", we can use Depth-First Search (DFS) to explore destinations. Because there might be "dead ends" (airports with no outgoing flights before we've used all our tickets), we need to use backtracking. If a path reaches a dead end before utilizing every ticket, we backtrack by un-marking the ticket, and try the next available destination.

Algorithm

1. Sort the tickets array first. This guarantees that when we build our adjacency list, the destinations will be in lexicographical order.
2. Build an adjacency list adj using a dictionary.
3. Initialize an array res with our starting point: ["JFK"].
4. Create a recursive helper function dfs(src):

• Base Case: If len(res) == len(tickets) + 1, we have successfully used every ticket! Return True.

• If src is not in adj or has no outgoing flights left, return False (we hit a dead end prematurely).

• Make a temporary copy of the current destinations for src.

• Loop through these destinations. For each destination:

• Remove it from adj[src] to mark the ticket as used.

• Append it to res.

• Recursively call dfs(destination). If it returns True, immediately return True (we found the optimal path!).

• Backtrack: Pop the destination from res and insert it back into adj[src] at the exact same index to try the next path.

• Return False if all branches fail.

5. Call dfs("JFK") and return res.

def find_itinerary(tickets: list[list[str]]) -> list[str]:
    # Sort to ensure lexical order preference
    tickets.sort()
    adj = defaultdict(list)
    
    for src, dst in tickets:
        adj[src].append(dst)
        
    res = ["JFK"]
    
    def dfs(src):
        if len(res) == len(tickets) + 1:
            return True
            
        if src not in adj:
            return False
            
        temp = list(adj[src])
        for i, v in enumerate(temp):
            # Mark ticket as used
            adj[src].pop(i)
            res.append(v)
            
            if dfs(v):
                return True
                
            # Backtrack
            adj[src].insert(i, v)
            res.pop()
            
        return False
        
    dfs("JFK")
    return res

Time & Space Complexity

• Time complexity: O(E^d)

• Reason: In the worst-case scenario (a highly connected graph with many dead ends), the backtracking DFS explores an exponential number of paths. E is the number of edges and d is the maximum number of outgoing flights from an airport.

• Space complexity: O(V + E)

• Reason: The adjacency list stores all Vertices and Edges. The recursion stack can grow up to the number of edges E.

Hierholzer's Algorithm (Optimal Eulerian Path)

Intuition

Since the problem guarantees that a valid itinerary using all tickets exists, we are essentially looking for an Eulerian Path (a trail in a finite graph that visits every edge exactly once).

Hierholzer's Algorithm solves this brilliantly without needing complex backtracking. The core realization is that we will only ever get stuck at a "dead end" airport if that airport is the final destination of our entire journey!

If we always take the lexicographically smallest flight, and we hit a dead end, we just add that dead end to our result list and backtrack up the recursion stack to explore the remaining untaken flights. Because we add airports to our result as we get "stuck" (post-order traversal), the path is built completely backwards. We simply reverse the list at the end.

To make grabbing the lexicographically smallest flight an O(1) operation, we can sort the adjacency list in descending order. This allows us to just .pop() from the end of the list!

Algorithm

1. Sort the tickets array in reverse lexicographical order.
2. Build the adjacency list adj. Because we sorted in reverse, appending destinations to the list ensures the smallest lexical destination is always at the very end.
3. Initialize an empty list res.
4. Define a recursive function dfs(src):

• While adj[src] is not empty:

• Pop the last element dst = adj[src].pop().

• Recursively call dfs(dst).

• Once a node has no more outgoing edges, append src to res.

5. Call dfs("JFK").
6. Reverse res and return it.

def find_itinerary(tickets: list[list[str]]) -> list[str]:
    adj = defaultdict(list)
    
    # Sort reverse lexicographically so we can pop from the end in O(1) time
    tickets.sort(reverse=True)
    
    for src, dst in tickets:
        adj[src].append(dst)
        
    res = []
    
    def dfs(src):
        # Visit all destinations in lexical order
        while adj[src]:
            dst = adj[src].pop()
            dfs(dst)
            
        # Add the airport only after all its outgoing flights are exhausted
        res.append(src)
        
    dfs("JFK")
    
    # The path was built backwards, so reverse it
    res.reverse()
    return res

Time & Space Complexity

• Time complexity: O(E log E)

• Reason: Sorting the tickets array takes O(E log E) time. Building the graph takes O(E). Hierholzer's algorithm visits every edge exactly once, taking O(E) time because .pop() is an O(1) operation. Overall time is strictly dominated by the sorting step.

• Space complexity: O(V + E)

• Reason: The adjacency list holds all Edges (tickets) and Vertices (airports). The recursion stack will grow up to O(E) depth.