Problem 37.5 · Advanced Graph AlgorithmsHard

Reconstruct Itinerary

What it teaches: Hierholzer's algorithm: post-order over consumed edges gives an Euler path.

Practise it on judges as “Reconstruct Itinerary”.

In plain words

You have a pile of plane tickets and must use every one, starting at JFK, choosing the alphabetically earliest airport whenever there's a choice. Keep flying along unused tickets until you're stuck; the place you get stuck goes at the end of the trip. Building the route backwards like this (Hierholzer's method) always uses every ticket.

Return the itinerary. Example: [[MUC,LHR],[JFK,MUC],[SFO,SJC],[LHR,SFO]] → [JFK, MUC, LHR, SFO, SJC].

The problem

Given airline tickets [from, to], use every ticket exactly once starting from "JFK". If several itineraries work, return the lexicographically smallest.

Example 1

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

Constraints

1 ≤ tickets ≤ 300
A valid itinerary exists

Pattern clues in the wording

→ Use every edge exactly once

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]	["JFK","MUC","LHR","SFO","SJC"]
2	tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]	["JFK","ATL","JFK","SFO","ATL","SFO"]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Hierholzer with min-heaps · O(E log E)

Hierholzer with min-heaps

Time O(E log E) Space O(E)

Map each airport to a PriorityQueue of destinations. DFS: while the queue isn't empty, poll and recurse; then add the airport to the front of the route.

▶ Dry run: Fly until stuck, then add to the fronttickets = [[MUC,LHR],[JFK,MUC],[SFO,SJC],[LHR,SFO]]

route(list)

empty

Step 1/4Each airport keeps its destinations in a min-heap (alphabetical). Start at JFK.

Approach 1

import java.util.*;

class Solution {
    private final Map<String, PriorityQueue<String>> g = new HashMap<>();
    private final LinkedList<String> route = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> t : tickets) g.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).add(t.get(1));
        visit("JFK");
        return route;
    }

    private void visit(String airport) {
        PriorityQueue<String> next = g.get(airport);
        while (next != null && !next.isEmpty()) visit(next.poll());
        route.addFirst(airport);
    }
}

Verdict: Dead ends are appended first, so they end up last.

Before you submit

Edge cases and common mistakes

Test these inputs

Repeated tickets
A dead-end branch that must be visited last

Mistakes people make

Greedy DFS without post-order (can get stuck before using all tickets).

Interview

Follow-up questions

When does an Euler circuit exist in an undirected graph?

Command Palette

The problem

Approaches

Hierholzer with min-heaps

Edge cases and common mistakes

Follow-up questions