#332

Hard

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Reconstruct Itinerary

Reconstruct Itinerary requires building a valid travel route using all tickets once, starting from JFK with lexical order preference.

depth first search graph eulerian circuit

Problem Statement

Given a list of airline tickets represented as pairs [from, to], reconstruct the complete itinerary starting from 'JFK'. Each ticket must be used exactly once, and the itinerary should prioritize the smallest lexical order when multiple valid routes exist.

Implement a function that returns the reconstructed itinerary as an array of airport codes, ensuring all tickets are consumed and the traversal follows the depth-first search pattern to form a valid Eulerian path.

Examples

Example 1

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

Output: ["JFK","MUC","LHR","SFO","SJC"]

Example details omitted.

Example 2

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]

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

Graph Construction

Build a directed graph where each node is an airport and edges are flights. Sort outgoing edges in lexical order to guarantee the smallest itinerary when traversing.

Depth-First Search Traversal

Perform DFS starting from 'JFK', recursively visiting the next lexical airport. Remove edges as they are used to avoid revisiting, effectively simulating ticket consumption.

Backtracking and Itinerary Formation

When reaching a node with no remaining outgoing edges, prepend it to the itinerary. Continue backtracking to assemble the full route in reverse order, ensuring all tickets are included exactly once.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(E log E) due to sorting adjacency lists, and space complexity is O(V + E) for the graph and recursive call stack, where V is airports and E is tickets.

What Interviewers Usually Probe

Candidate identifies graph representation with adjacency lists.
Candidate sorts destinations to handle lexical order correctly.
Candidate uses DFS and recognizes Eulerian path formation with backtracking.

Common Pitfalls or Variants

Common pitfalls

Failing to sort adjacency lists leading to incorrect lexical order.
Not removing edges after visiting, causing repeated use of the same ticket.
Appending instead of prepending during backtracking, yielding reversed itinerary.

Follow-up variants

Allowing multiple starting airports instead of fixed 'JFK'.
Returning all possible valid itineraries instead of just the smallest lexical order.
Using BFS instead of DFS for traversal with priority queue for lexical order.

FAQ

What is the main pattern used in Reconstruct Itinerary?

The primary pattern is depth-first search on a directed graph to form an Eulerian path while respecting lexical order.

Why is sorting destinations important?

Sorting ensures that among multiple possible flights, the itinerary with the smallest lexical order is chosen consistently.

Can I use BFS instead of DFS for this problem?

DFS is preferred because it naturally handles backtracking and constructing the Eulerian path correctly.

How do I handle tickets with the same departure?

Maintain a sorted list of destinations for each departure and remove edges as tickets are used to avoid duplicates.

What should I do if the itinerary appears reversed?

Prepend nodes during backtracking instead of appending to build the correct order from start to end.

terminal

Solution

Solution 1: Eulerian Path

The problem is essentially about finding a path that starts from a specified starting point, passes through all the edges exactly once, and has the smallest lexicographical order among all such paths, given $n$ vertices and $m$ edges. This is a classic Eulerian path problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        def dfs(f: str):
            while g[f]:
                dfs(g[f].pop())
            ans.append(f)

        g = defaultdict(list)
        for f, t in sorted(tickets, reverse=True):
            g[f].append(t)
        ans = []
        dfs("JFK")
        return ans[::-1]

Continue Practicing

#753 cracking the safe #329 longest increasing path in a matrix #310 minimum height trees