Log inSign up
hardLeetCodeNot Started

Reconstruct Itinerary

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Define Eulerian Paths and Circuits in directed multigraphs.
  • Implement Hierholzer's algorithm using post-order DFS edge consumption.
  • Order edges lexicographically using priority queues / heaps.
  • Avoid dead-end traps in Eulerian traversal by appending nodes during backtracking.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever a problem asks to 'use every ticket/edge exactly once' in a directed graph starting from a specific node, and break ties with lexicographical order, model it as an Eulerian Path and solve with Hierholzer's Algorithm.

1. DFS Backtracking with Ticket Consumption

Intuition

Sort all tickets lexicographically. Run DFS with backtracking starting from JFK. At each step, try every unused ticket departing from the current airport in lexicographical order. The first path that successfully uses all tickets (path length == tickets.length + 1) is the lexicographically smallest Eulerian path.

Algorithm

  1. Sort tickets lexicographically.
  2. Track used tickets with a boolean array used of size E.
  3. Define dfs(curr, count, path):
  4. If count == tickets.length:
  5. Save path and return true.
  6. For each ticket i departing from curr:
  7. If !used[i]:
  8. used[i] = true
  9. path.push(ticket.to)
  10. If dfs(ticket.to, count + 1, path) return true.
  11. path.pop(), used[i] = false (backtrack)
  12. Return false.
  13. Run dfs("JFK", 0, ["JFK"]).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6bool dfsBacktrack(const std::string& curr, int usedCount, int totalTickets,
7 std::vector<std::vector<std::string>>& tickets,
8 std::vector<bool>& used, std::vector<std::string>& path) {
9 if (usedCount == totalTickets) return true;
10
11 for (size_t i = 0; i < tickets.size(); ++i) {
12 if (!used[i] && tickets[i][0] == curr) {
13 used[i] = true;
14 path.push_back(tickets[i][1]);
15 if (dfsBacktrack(tickets[i][1], usedCount + 1, totalTickets, tickets, used, path)) {
16 return true;
17 }
18 path.pop_back();
19 used[i] = false;
20 }
21 }
22 return false;
23}
24
25std::vector<std::string> findItineraryBacktrack(std::vector<std::vector<std::string>>& tickets) {
26 std::sort(tickets.begin(), tickets.end());
27 std::vector<bool> used(tickets.size(), false);
28 std::vector<std::string> path = {"JFK"};
29 dfsBacktrack("JFK", 0, tickets.size(), tickets, used, path);
30 return path;
31}
32
33int main() {
34 std::vector<std::vector<std::string>> tickets = {
35 {"MUC","LHR"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"}
36 };
37 auto res = findItineraryBacktrack(tickets);
38 std::cout << "Itinerary (Backtrack): ";
39 for (const auto& s : res) std::cout << s << " ";
40 std::cout << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(E!) in the worst-case when many dead ends require extensive backtracking.
  • Space complexity: O(E) for the recursion stack and path array.

2. Iterative Hierholzer's Algorithm with Stack

Intuition

Simulate Hierholzer's algorithm using an explicit stack rather than recursion. Start at JFK. Keep advancing to the lexicographically smallest neighbor, pushing visited nodes to a traversal stack. When a node has no outgoing edges, pop it from the traversal stack and append it to the itinerary list. Finally, reverse the itinerary list.

Algorithm

  1. Build an adjacency list where each node has a list of sorted destinations.
  2. Initialize traversal stack st = ["JFK"], itinerary = [].
  3. While st is not empty:
  4. curr = st.top()
  5. If adj[curr] is not empty:
  6. Pop the first (smallest) neighbor next from adj[curr].
  7. Push next to st.
  8. Else:
  9. Pop curr from st, append curr to itinerary.
  10. Reverse itinerary and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <algorithm>
6#include <stack>
7
8std::vector<std::string> findItineraryIterative(std::vector<std::vector<std::string>>& tickets) {
9 // Sort destinations descending so we can pop_back() smallest in O(1)
10 std::unordered_map<std::string, std::vector<std::string>> adj;
11 for (const auto& t : tickets) {
12 adj[t[0]].push_back(t[1]);
13 }
14 for (auto& [u, list] : adj) {
15 std::sort(list.rbegin(), list.rend());
16 }
17
18 std::stack<std::string> st;
19 st.push("JFK");
20 std::vector<std::string> itinerary;
21
22 while (!st.empty()) {
23 std::string curr = st.top();
24 if (adj.count(curr) && !adj[curr].empty()) {
25 std::string next = adj[curr].back();
26 adj[curr].pop_back();
27 st.push(next);
28 } else {
29 itinerary.push_back(curr);
30 st.pop();
31 }
32 }
33
34 std::reverse(itinerary.begin(), itinerary.end());
35 return itinerary;
36}
37
38int main() {
39 std::vector<std::vector<std::string>> tickets = {
40 {"JFK","SFO"},{"JFK","ATL"},{"SFO","ATL"},{"ATL","JFK"},{"ATL","SFO"}
41 };
42 auto res = findItineraryIterative(tickets);
43 std::cout << "Itinerary (Iterative): ";
44 for (const auto& s : res) std::cout << s << " ";
45 std::cout << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(E log E) to sort edges, plus O(E) to traverse edges.
  • Space complexity: O(V + E) for the adjacency list and stacks.

3. Hierholzer's Algorithm (Recursive Post-Order Eulerian Path)

Intuition

Hierholzer's algorithm discovers an Eulerian path by advancing along edges until reaching a dead end. In an Eulerian graph, a dead end can only occur at the true end of the itinerary! By adding each node to the itinerary upon recursion exit (post-order), earlier sub-cycles are cleanly spliced into the main path. Reversing the result produces the globally optimal Eulerian path.

Algorithm

  1. Store the graph in a map where each departure airport maps to a Min-PriorityQueue of arrivals.
  2. Define dfs(curr):
  3. While adj[curr] is not empty:
  4. Pop the smallest destination next = adj[curr].poll()
  5. dfs(next)
  6. itinerary.push_back(curr) (post-order placement)
  7. Call dfs("JFK").
  8. Reverse itinerary and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <queue>
6#include <algorithm>
7
8void hierholzer(const std::string& curr,
9 std::unordered_map<std::string, std::priority_queue<std::string, std::vector<std::string>, std::greater<std::string>>>& adj,
10 std::vector<std::string>& itinerary) {
11 while (!adj[curr].empty()) {
12 std::string next = adj[curr].top();
13 adj[curr].pop();
14 hierholzer(next, adj, itinerary);
15 }
16 itinerary.push_back(curr);
17}
18
19std::vector<std::string> findItinerary(std::vector<std::vector<std::string>>& tickets) {
20 std::unordered_map<std::string, std::priority_queue<std::string, std::vector<std::string>, std::greater<std::string>>> adj;
21 for (const auto& t : tickets) {
22 adj[t[0]].push(t[1]);
23 }
24
25 std::vector<std::string> itinerary;
26 hierholzer("JFK", adj, itinerary);
27 std::reverse(itinerary.begin(), itinerary.end());
28 return itinerary;
29}
30
31int main() {
32 std::vector<std::vector<std::string>> tickets = {
33 {"JFK","SFO"},{"JFK","ATL"},{"SFO","ATL"},{"ATL","JFK"},{"ATL","SFO"}
34 };
35 auto res = findItinerary(tickets);
36 std::cout << "Optimal Itinerary (Hierholzer): ";
37 for (const auto& s : res) std::cout << s << " ";
38 std::cout << std::endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(E log E) because each ticket is inserted and removed from a priority queue of size at most E.
  • Space complexity: O(V + E) for the adjacency priority queues and recursion stack.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS BacktrackingO(E!)O(E)Intuitive greedy attempt with backtrack undo.Worst-case factorial time; times out on graph configurations with many dead ends.
2.Iterative HierholzerO(E log E)O(V + E)Eliminates recursion stack using an explicit traversal stack.Requires sorting lists in reverse to achieve O(1) pop operations.
3.Recursive Hierholzer (PriorityQueue)OptimalO(E log E)O(V + E)Clean, elegant, textbook optimal Eulerian path implementation in under 20 lines.Uses recursion stack of depth E.

Common Pitfalls & Crucial Edge Cases

Pushing nodes to the itinerary before exploring neighbors.

Hierholzer's algorithm must push the node to the itinerary strictly AFTER exploring all its outgoing edges (post-order).

Forgetting to reverse the itinerary array at the end.

Post-order pushes the final destination first and JFK last; reversing restores the forward order.

Crucial Edge Cases to Validate:

  • Cycles in the graph (e.g. JFK -> ATL -> JFK) — Hierholzer's algorithm naturally explores and splices the cycle before proceeding to the final destination.
  • Multiple duplicate tickets between the same two airports (multigraph) — Priority queue cleanly holds duplicate arrival entries and dequeues them one by one.
  • Dead end that is reached early — Post-order insertion pushes the dead end to the back of the result list, preserving the correct path.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Name the algorithm right away: 'This is an Eulerian Path problem on a directed multigraph, solvable using Hierholzer's algorithm in O(E log E) time.'
  2. Explain the post-order intuition: 'We only commit a vertex to the itinerary when it has no remaining outgoing edges, ensuring dead ends are positioned at the end of the journey.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does simple greedy DFS without post-order backtracking fail on some ticket inputs?

2.What is an Eulerian Path?

3.What is the time complexity of Hierholzer's Algorithm using a Min-PriorityQueue for edges?

Back to DSA Sheet