Reconstruct Itinerary

Asked byUberFacebookGoogleAmazonTwitterNetflix

Problem

Given a list of airline tickets as [from, to] pairs, reconstruct and return the itinerary — starting from "JFK" — that uses every ticket exactly once. If multiple valid itineraries exist, return the lexicographically smallest one.

Examples

Example 1

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

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

Constraints

1 <= tickets.length <= 300

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Advanced Graphs pattern

Beyond basic traversal, some graph problems need ordering constraints (topological sort) or weighted shortest paths (Dijkstra, Bellman-Ford, minimum spanning trees).

Look for this pattern when

The problem has ordering or prerequisite constraints ("do X before Y").
Edges have weights or costs and you need the cheapest path, not just any path.

Read the full Advanced Graphs guide →

Video walkthroughs

Original problem on LeetCode ↗