Hard — Graph | Depth-First Search | Eulerian Path | Backtracking

The Problem

Given a list of airline tickets represented as pairs of departure and arrival airports, return the itinerary in order starting from JFK, using all tickets exactly once.

Approach

Build a graph from tickets sorted in reverse lexicographical order, then use DFS with Hierholzer’s algorithm to find the Eulerian path. The algorithm uses a stack-based approach where we traverse as deep as possible and add nodes to the result in reverse order.

Time: O(E log E) · Space: O(E)

Code

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)

        for start, end in sorted(tickets, reverse=True):
            graph[start].append(end)

        route = []

        def dfs(node):
            while graph[node]:
                dfs(graph[node].pop())
            route.append(node)

        dfs("JFK")

        return route[::-1]

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment