Reconstruct Itinerary

Problem

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

Constraints:

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

Solution

Approach: Hierholzer’s Algorithm (Eulerian Path)

The key insight is that this is an Eulerian path problem - we need to visit every edge (ticket) exactly once. We use DFS with post-order traversal.

Implementation

from collections import defaultdict, deque

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        # Build graph with destinations sorted lexically
        graph = defaultdict(list)
        for src, dst in sorted(tickets, reverse=True):
            graph[src].append(dst)

        route = []

        def dfs(airport):
            # Visit all destinations from this airport
            while graph[airport]:
                next_dest = graph[airport].pop()
                dfs(next_dest)
            # Add to route in post-order (reverse order)
            route.append(airport)

        dfs("JFK")
        return route[::-1]

Alternative Implementation (Iterative)

from collections import defaultdict

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        # Build graph
        graph = defaultdict(list)
        for src, dst in sorted(tickets, reverse=True):
            graph[src].append(dst)

        stack = ["JFK"]
        route = []

        while stack:
            # Peek at top airport
            while graph[stack[-1]]:
                next_dest = graph[stack[-1]].pop()
                stack.append(next_dest)
            # No more destinations from this airport
            route.append(stack.pop())

        return route[::-1]

Complexity Analysis

Time Complexity: O(E log E), where E is number of tickets. Sorting tickets dominates.
Space Complexity: O(E) for the graph and recursion stack.

Key Insights

Eulerian Path: The problem asks for an Eulerian path - a path that visits every edge exactly once.
Post-Order Traversal: We add airports to result in post-order (after visiting all destinations), then reverse to get correct order.
Lexical Ordering: By sorting tickets in reverse order and using pop() (which removes from end), we process destinations in lexical order.
Guaranteed Solution: The problem guarantees a valid itinerary exists, so we don’t need to handle impossible cases.
Dead Ends First: The algorithm naturally handles dead ends by visiting them first (post-order), ensuring we don’t get stuck.
Graph as Adjacency List: Each airport maps to a list of destinations (which can have duplicates if multiple tickets).