Reconstruct Itinerary

1. Define the problem

You are given a list of airline tickets, each written as [from, to]. Put them in order into a single trip that starts at JFK and uses every ticket exactly once . If several such trips exist, return the one that comes first in alphabetical order when read as a list of airport codes. A valid trip is guaranteed to exist. This is an Eulerian path : a route that walks every edge once. Greedily flying to the alphabetically smallest airport you can, and recording an airport only once it has no tickets left, builds that route backwards. Reverse the record at the end.

Constraints

1 ≤ tickets.length ≤ 300
Every airport code is exactly three uppercase letters
The same pair may appear more than once, meaning two tickets on the same route
At least one valid trip starting from JFK always exists

Example

Inputtickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]

Output["JFK", "MUC", "LHR", "SFO", "SJC"]

Explanation Each airport offers exactly one onward ticket, so the trip is forced: JFK to MUC to LHR to SFO to SJC.

2. Know the words first

In plain terms

Eulerian path: A route through a graph that uses every edge exactly once. It may visit the same node many times, which is why a plain visited list does not work here.
Hierholzer’s algorithm: The standard way to build an Eulerian path: keep flying until you get stuck, write down the airport you got stuck at, then back up and carry on.
Dead end: An airport with no unused tickets leaving it. In a valid input there is exactly one, and it has to be the very last stop.
Lexical order: Dictionary order for text. "ATL" comes before "SFO", so a tie between the two is always broken in favour of ATL.

3. Visualize the solution

The stack of airports you are currently standing on, deepest at the left

s0JFK

s1—

s2—

s3—

s4—

Statusinit

Every trip starts at JFK, so JFK is the only airport on the stack.

What happens in this step

tickets = [["MUC","LHR"], ["JFK","MUC"], ["SFO","SJC"], ["LHR","SFO"]]
onward tickets: JFK -> MUC, MUC -> LHR, LHR -> SFO, SFO -> SJC
stack = [JFK]
route = []

Each airport has exactly one ticket out, so there is nothing to choose between.

Step 1 of 7

Steps to visualize

The row is the stack, not the map. Cell s0 is the airport you started at and each cell to the right is one flight further along.
A dash means that slot is empty right now.
Look at the airport on top of the stack. If it still has an unused ticket, take the alphabetically smallest one and push that airport on.
If it has none left, that airport is a dead end: pop it and write it into the route.
The route is built back to front, so reversing it at the end gives the trip in flying order.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The stack of airports you are currently standing on, deepest at the left

s0JFK

s1—

s2—

s3—

s4—

Statusinit

Every trip starts at JFK, so JFK is the only airport on the stack.

What happens in this step

tickets = [["MUC","LHR"], ["JFK","MUC"], ["SFO","SJC"], ["LHR","SFO"]]
onward tickets: JFK -> MUC, MUC -> LHR, LHR -> SFO, SFO -> SJC
stack = [JFK]
route = []

Each airport has exactly one ticket out, so there is nothing to choose between.

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

function findItinerary(tickets) {
  const graph = new Map();

  for (const ticket of tickets) {
    if (!graph.has(ticket[0])) {
      graph.set(ticket[0], []);
    }

    graph.get(ticket[0]).push(ticket[1]);
  }

  for (const destinations of graph.values()) {
    destinations.sort();
    destinations.reverse();
  }

  const route = [];
  const stack = ['JFK'];

  while (stack.length > 0) {
    const airport = stack[stack.length - 1];
    const destinations = graph.get(airport);

    if (destinations && destinations.length > 0) {
      stack.push(destinations.pop());
    } else {
      route.push(stack.pop());
    }
  }

  return route.reverse();
}

Time: O(e log e), where e is the number of tickets
Space: O(e)

6. Test cases

Test cases

Input	Expected	Covers
`tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]`	`["JFK", "MUC", "LHR", "SFO", "SJC"]`	example from the docstring, one forced route
`tickets = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]`	`["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]`	two choices out of JFK, broken by alphabetical order
`tickets = [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]`	`["JFK", "NRT", "JFK", "KUL"]`	the alphabetically first choice is a dead end, so the answer is built in reverse
`tickets = [["JFK", "SFO"]]`	`["JFK", "SFO"]`	smallest possible input, one ticket
`tickets = [["JFK", "ATL"], ["ATL", "JFK"]]`	`["JFK", "ATL", "JFK"]`	a round trip that returns to the airport it started at
`tickets = [["JFK", "AAA"], ["AAA", "JFK"], ["JFK", "BBB"]]`	`["JFK", "AAA", "JFK", "BBB"]`	JFK is left twice, so the same airport appears more than once

Reconstruct Itinerary