Log inSign up
mediumLeetCodeNot Started

Itinerary from Tickets

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

Graph
Solve on LeetCode
Lesson

Problem Statement

Given a list of airline tickets represented as pairs of departure and arrival airports tickets = [[from1, to1], [from2, to2], ...], reconstruct the complete itinerary from the starting city to the destination.

You are guaranteed that the tickets form a single continuous non-branching itinerary with no cycles (a linear directed path). Find the starting departure city and output the complete sequence of cities in order.

Constraints:

  • 1 <= tickets.length <= 105
  • tickets[i].length == 2
  • Each airport name is a non-empty string.
  • Tickets are guaranteed to form a single continuous valid path without cycles.

What You'll Learn

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

  • Identify the source of a directed linear path using Set differences (in-degree 0).
  • Reconstruct sequential journeys using Hash Maps.
  • Achieve linear O(N) time and space complexity.
  • Distinguish linear chain reconstruction from Eulerian path problems (like Hierholzer's).

Pattern Recognition Trigger

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

Signals to Look For:

  • Whenever given a set of directed edge pairs forming a linear chain without branches, find the head of the list by checking outDegree == 1 && inDegree == 0 (in from set but not in to set).

1. Repeated Linear Search for Starting City

Intuition

For each ticket [from, to], check if from appears as a destination in any other ticket by linearly scanning all tickets. The ticket whose departure city never appears as a destination is the starting ticket. Then sequentially match destinations.

Algorithm

  1. For each ticket t in tickets:
  2. Check if t.from is present in any other ticket's to field.
  3. If not present, start = t.from.
  4. Reconstruct path by repeatedly scanning tickets for matching departures.
  5. Return list of cities.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5std::vector<std::string> itineraryBrute(const std::vector<std::pair<std::string, std::string>>& tickets) {
6 int n = tickets.size();
7 std::string start = "";
8
9 for (int i = 0; i < n; ++i) {
10 bool isArrival = false;
11 for (int j = 0; j < n; ++j) {
12 if (tickets[i].first == tickets[j].second) {
13 isArrival = true;
14 break;
15 }
16 }
17 if (!isArrival) {
18 start = tickets[i].first;
19 break;
20 }
21 }
22
23 std::vector<std::string> result = {start};
24 std::string curr = start;
25
26 for (int step = 0; step < n; ++step) {
27 for (int i = 0; i < n; ++i) {
28 if (tickets[i].first == curr) {
29 curr = tickets[i].second;
30 result.push_back(curr);
31 break;
32 }
33 }
34 }
35 return result;
36}
37
38int main() {
39 std::vector<std::pair<std::string, std::string>> tickets = {
40 {"Chennai", "Bangalore"}, {"Bombay", "Delhi"}, {"Goa", "Chennai"}, {"Delhi", "Goa"}
41 };
42 auto res = itineraryBrute(tickets);
43 std::cout << "Itinerary (Brute): ";
44 for (auto& s : res) std::cout << s << " -> ";
45 std::cout << "END
46";
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N^2) due to quadratic linear searches across all tickets.
  • Space complexity: O(N) for the resulting itinerary array.

2. Degree Counting with Hash Map

Intuition

Maintain an inDegree map for every airport. Increment in-degree when an airport appears as a destination. The starting airport is the departure airport with in-degree equal to 0.

Algorithm

  1. Store tickets in a map adj[from] = to.
  2. Store in-degrees of all airports in a map inDegree.
  3. Find the airport s where inDegree[s] == 0 and s is present in adj.
  4. Traverse adj from s to assemble the full journey.
  5. Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5
6std::vector<std::string> itineraryDegree(const std::vector<std::pair<std::string, std::string>>& tickets) {
7 std::unordered_map<std::string, std::string> nextCity;
8 std::unordered_map<std::string, int> inDegree;
9
10 for (const auto& [from, to] : tickets) {
11 nextCity[from] = to;
12 inDegree[to]++;
13 if (inDegree.find(from) == inDegree.end()) {
14 inDegree[from] = 0;
15 }
16 }
17
18 std::string start = "";
19 for (const auto& [city, deg] : inDegree) {
20 if (deg == 0 && nextCity.find(city) != nextCity.end()) {
21 start = city;
22 break;
23 }
24 }
25
26 std::vector<std::string> result = {start};
27 std::string curr = start;
28 while (nextCity.find(curr) != nextCity.end()) {
29 curr = nextCity[curr];
30 result.push_back(curr);
31 }
32 return result;
33}
34
35int main() {
36 std::vector<std::pair<std::string, std::string>> tickets = {
37 {"Chennai", "Bangalore"}, {"Bombay", "Delhi"}, {"Goa", "Chennai"}, {"Delhi", "Goa"}
38 };
39 auto res = itineraryDegree(tickets);
40 std::cout << "Itinerary (Degree): ";
41 for (auto& s : res) std::cout << s << " -> ";
42 std::cout << "END
43";
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N) linear time using hash maps.
  • Space complexity: O(N) to store in-degrees and adjacency maps.

3. Hash Set Difference + Map Traversal

Intuition

Construct a map nextCity[from] = to and a set of all destination airports destinations. The starting city is simply the departure city that does not exist in destinations. Once found, traverse the map until the destination city is reached. This achieves optimal O(N) runtime with minimal memory allocation.

Algorithm

  1. Initialize nextCity map and destinations set.
  2. For each ticket [from, to]:
  3. nextCity[from] = to
  4. destinations.insert(to)
  5. Find the start city: iterate over keys in nextCity, find the key not in destinations.
  6. Initialize itinerary = [start].
  7. While curr is present in nextCity:
  8. curr = nextCity[curr]
  9. itinerary.push(curr)
  10. Return itinerary.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <unordered_set>
6
7std::vector<std::string> reconstructItinerary(const std::vector<std::pair<std::string, std::string>>& tickets) {
8 std::unordered_map<std::string, std::string> nextCity;
9 std::unordered_set<std::string> destinations;
10
11 for (const auto& [from, to] : tickets) {
12 nextCity[from] = to;
13 destinations.insert(to);
14 }
15
16 std::string start = "";
17 for (const auto& [from, to] : nextCity) {
18 if (destinations.find(from) == destinations.end()) {
19 start = from;
20 break;
21 }
22 }
23
24 std::vector<std::string> itinerary;
25 std::string curr = start;
26 itinerary.push_back(curr);
27
28 while (nextCity.find(curr) != nextCity.end()) {
29 curr = nextCity[curr];
30 itinerary.push_back(curr);
31 }
32
33 return itinerary;
34}
35
36int main() {
37 std::vector<std::pair<std::string, std::string>> tickets = {
38 {"Chennai", "Bangalore"}, {"Bombay", "Delhi"}, {"Goa", "Chennai"}, {"Delhi", "Goa"}
39 };
40 auto res = reconstructItinerary(tickets);
41 std::cout << "Optimal Itinerary: ";
42 for (size_t i = 0; i < res.size(); ++i) {
43 std::cout << res[i] << (i + 1 < res.size() ? " -> " : "
44");
45 }
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N) where N is the number of tickets. Building map/set takes O(N), finding start takes O(N), path walk takes O(N).
  • Space complexity: O(N) to store the nextCity map and destinations set.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Pair ScanningO(N^2)O(N)No hash maps or external data structures needed.Quadratic time complexity; fails for large ticket counts.
2.In-Degree CountingO(N)O(N)Formal in-degree tracking.Stores integer counts for every city.
3.Set Difference + Map TraversalOptimalO(N)O(N)Simplest, cleanest, and fastest O(N) solution with minimal operations.Requires hash map and hash set.

Common Pitfalls & Crucial Edge Cases

Assuming the first ticket in the input array is always the starting ticket.

Tickets are randomly shuffled; you must compute the starting city by checking which departure airport never appears as an arrival.

Using quadratic scans instead of a Hash Set for destination lookups.

Use a HashSet to check containment in O(1) time.

Crucial Edge Cases to Validate:

  • N = 1 (Single ticket: ['A', 'B']) — Start is A, returns [A, B].
  • Long chain of 10^5 tickets — Runs smoothly in linear O(N) time and space in under 50ms.
  • Tickets given in reverse or shuffled order — Map and set lookups are order-independent; finds the true origin regardless of input order.

Interview Tips & Best Practices

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

  1. State the graph theory property: 'In a directed path with no cycles, the source is the unique vertex with in-degree 0 and out-degree 1.'
  2. Distinguish this simple linear reconstruction from an Eulerian path (LC 332): clarify whether tickets can branch or contain cycles.

Quick Comprehension Check

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

1.Why is the starting city guaranteed to be absent from the destinations set?

2.How is this problem different from LeetCode 332 (Reconstruct Itinerary)?

3.What is the time complexity of the optimal Set Difference approach?

Back to DSA Sheet