Katkat
Back

Reconstruct an Itinerary from Flight Tickets

PinterestSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Tests graph modeling, depth-first search (DFS), and Hierholzer's algorithm to construct an Eulerian path with lexicographical tie-breaking.

Problem Statement

You are given a list of airline tickets where each ticket is represented as a pair of airport codes [from_airport, to_airport]. Each ticket represents a one-way flight from from_airport to to_airport.

Reconstruct the complete travel itinerary in order, subject to the following rules:

  1. All tickets must be used exactly once.
  2. The itinerary must start at "JFK".
  3. There may be duplicate tickets (identical origin and destination).
  4. If there are multiple valid itineraries, return the itinerary that has the smallest lexical order when read as a single list of airport codes (e.g., ["JFK", "LGA"] has a smaller lexical order than ["JFK", "SFO"]).
  5. You may assume that at least one valid itinerary that uses all tickets exists.

Function Signature

def find_itinerary(tickets: list[list[str]]) -> list[str]:
    pass

Input & Output

  • Input: tickets, a list of pairs where each element is a list of two 3-letter uppercase strings [origin, destination].
  • Output: A list of airport code strings representing the full sequence of visited airports in order.

Constraints

  • 1 <= len(tickets) <= 10,000
  • tickets[i].length == 2
  • tickets[i][0].length == 3 and tickets[i][1].length == 3
  • Each airport code consists solely of uppercase English letters.
  • It is guaranteed that a valid Eulerian path starting from "JFK" exists.

Examples

Example 1

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Explanation: The only way to use all tickets starting from "JFK" is JFK -> MUC -> LHR -> SFO -> SJC.

Example 2

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another valid path is ["JFK","SFO","ATL","JFK","ATL","SFO"], but ["JFK","ATL", ...] is lexicographically smaller.

Edge Cases to Consider

  • Dead ends: Greedily choosing the lexicographically smallest neighbor might lead to an airport with no outgoing flights before visiting all tickets.
  • Duplicate tickets: Multiple identical tickets between the same two airports must each be used.
  • Cycles: Paths may visit the same airport multiple times.

Hints

Hint 1

Treat this as finding an Eulerian path in a directed multigraph, starting at node 'JFK'.

Hint 2

Sort outgoing edges lexicographically so that when you explore, you naturally favor smaller destinations first.

Hint 3

Use Hierholzer's algorithm (post-order DFS traversal): append a node to the itinerary only after all its outgoing edges have been exhausted, then reverse the result.

Follow-up questions

  • How would your algorithm change if a valid itinerary is not guaranteed to exist?
  • How can you implement this iteratively using an explicit stack instead of recursion to prevent call stack overflow for large graphs?
  • What is the time and space complexity if there are E edges and V vertices?