Reconstruct Itinerary

Find the lexicographically smallest valid flight itinerary from a list of tickets.

graph backtracking dfs sorting

You are given a list of airline tickets where each ticket is a pair of strings [from, to] representing a flight from one airport to another. You must reconstruct the itinerary in order. All flights must be used exactly once, and the itinerary must start at airport "JFK".

If there are multiple valid itineraries, return the one that is lexicographically smallest as a list of airport codes. A list A is lexicographically smaller than list B if at the first index where they differ, A[i] < B[i] (as strings). You may assume that at least one valid itinerary always exists.

Write a function `reconstruct_itinerary(tickets)` that takes a list of ticket lists `tickets` (e.g., `[["JFK","SFO"], ["JFK","ATL"], ...]`) and returns the reconstructed itinerary as a list of strings.

Implementation details: You can use any approach (backtracking, DFS, Hierholzer's algorithm). The solution must be deterministic and produce the lexicographically smallest itinerary.

Constraints

- 1 <= len(tickets) <= 300
- Each ticket is a list of exactly two strings: [from, to].
- Airport codes consist of uppercase English letters only, length 3.
- At least one valid itinerary exists.

Example

>>> reconstruct_itinerary([["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]])
['JFK', 'ATL', 'JFK', 'SFO', 'ATL', 'SFO']

>>> reconstruct_itinerary([["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]])
['JFK', 'NRT', 'JFK', 'KUL']

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Build a graph where each airport maps to a list of destinations, sorted in reverse lexicographic order so you pop the smallest first.

Use a depth-first search that removes edges as you go, and append airports on the post-order (after visiting all neighbors).

At the end, reverse the collected list to obtain the correct starting order.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.