Rebuild the Travel Log

MediumAdvanced Graphs

Problem

A consultant lost her travel diary but kept every boarding pass. Each passes[i] = [from, to] is one flight between airport codes. She knows the trip started at airport start and that she used every boarding pass exactly once.

Rebuild the sequence of airports she visited. Several sequences may fit; return the one that is lexicographically smallest when compared airport by airport. At least one valid sequence is guaranteed.

Example 1

Input:
start = "OSL", passes = [["OSL","ROM"],["ROM","OSL"],["OSL","BER"]]
Output:
["OSL","ROM","OSL","BER"]

"BER" is smaller than "ROM", but flying to BER first would strand the two other passes. The smallest valid sequence goes to ROM first.

Example 2

Input:
start = "LIS", passes = [["LIS","MAD"],["MAD","PAR"]]
Output:
["LIS","MAD","PAR"]

Example 3

Input:
start = "AAA", passes = [["AAA","BBB"],["AAA","CCC"],["BBB","AAA"],["CCC","AAA"]]
Output:
["AAA","BBB","AAA","CCC","AAA"]

Constraints

  • 1 ≤ passes.length ≤ 10^4
  • Airport codes are non-empty strings of uppercase letters and digits.
  • A valid sequence using all passes from start exists.

Hint

Show the first hint

Each pass is a directed edge used exactly once: you are looking for an Eulerian path.

Walkthrough

How to approach it

01Clarify before coding

  • Must every pass be used? Yes, exactly once.
  • Can the same pass appear twice? Yes, duplicates are separate flights.
  • How is 'lexicographically smallest' compared? Airport by airport, using normal string order.

02Brute force

Backtracking DFS: try destinations in sorted order, undo when you get stuck, return the first full itinerary.

Cost: Usually fast, but worst case exponential when many wrong branches each use most passes before failing.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.