Reconstruct Itinerary

The problem

You are given tickets, a list of airline tickets. Each ticket is a pair [from, to] of airport codes and pays for one flight in that direction. Plan a trip that starts at JFK and uses every ticket exactly once, and return the airports in the order you visit them, JFK first. The same ticket can be in the list more than once, and each copy must be used. A valid trip always exists. If several trips are valid, compare them airport by airport and return the one with the alphabetically smaller code at the first place where they differ.

What to write

function solve(tickets: string[][]): string[]

Input
tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

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

Input
tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]

Output
["JFK","NRT","JFK","KUL"]

Constraints

Duplicate tickets are distinct uses; a valid itinerary exists.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A valid trip always exists, so you never have to prove that one is possible. You may pass through the same airport many times, but each ticket is used once. So the thing to keep track of is which tickets are still unused, not which airports you have seen.

2. Hint 2: Ask a smaller question

   Look at example 2. Two tickets leave JFK, and KUL is the smaller code. What goes wrong if you fly to KUL first? No ticket leaves KUL, so at which point of a complete trip must the ticket to KUL be used?

3. Hint 3: Name the pattern

   Airports are points and tickets are one-way links, and the trip must walk every link exactly once. That is a graph traversal with a visited set, where the things you mark as used are the tickets, not the airports. A walk that uses every link once is called an Eulerian path; the method here is known as Hierholzer's algorithm. Read the lesson on graph traversal with a visited set.

4. Hint 4: State the invariant

   The stack holds the path you are on, from JFK to the airport you are at now. An airport leaves the stack only when it has no unused ticket, and at that moment it is written to the route. So the route is filled from the last airport of the trip back to the first.

5. Hint 5: Sketch the pseudocode

   List each airport's destinations, sorted so that the smallest can be taken first. Push JFK on a stack. While the stack is not empty: if the top airport has a ticket left, take the smallest destination off its list and push that destination. Otherwise pop the airport and append it to the route. Return the route reversed.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Use Hierholzer’s algorithm, consuming the smallest available destination and recording airports only when no unused outgoing ticket remains.

The slow way

From JFK, try the unused tickets one at a time, smallest destination first, and go on from wherever you land. If you get stuck before every ticket is used, undo the last flight and try the next ticket. The first complete trip is the answer. It is correct, but one wrong early choice can be explored for a very long time before it is undone.

The insight

You only get stuck at an airport when all its tickets are used. The first time that happens, you are at the airport where the trip has to end, because everywhere else a ticket out is still waiting whenever you arrive. So getting stuck is not a mistake. Write that airport down as the end of the trip, step back, and carry on. This is known as Hierholzer's algorithm.

Step by step

1. Group the tickets: for each airport, list where its tickets go. At every airport you need to know which flights you can still take from there. One list per departure airport answers that without searching through all the tickets again.
2. Sort each list in reverse, so the smallest code is at the end. The smallest code, the first in alphabetical order, has to be tried first to get the smallest trip. Taking an item off the end of a list is fast, so the smallest is put there.
3. Start at JFK with a stack for the current path and an empty route. A stack is a pile that you add to and take from at the top only. The top is the airport you are at now, and below it are the airports you came through.
4. Look at the tickets still unused at the airport on top of the stack. What is left in that airport's list decides the next move: fly on, or step back. An airport that no ticket leaves has no list at all, which counts as nothing left.
5. A ticket is left: use the smallest one and move to that airport. Taking the destination out of the list marks the ticket as used, so it cannot be flown twice. Airports are never marked: the trip may land at the same airport many times. The destination becomes the top of the stack.
6. No ticket is left: move this airport from the stack to the route. Every flight out of this airport has been used, so whatever comes after it in the trip is already in the route. The airport can be written down, and the airport below it is on top again.
7. The route was written from the end backwards, so return it reversed. The first airport written was the last one of the trip, and JFK, at the bottom of the stack, was written last. Reversing puts the airports in flying order.

The same numbered steps are the comments in each solution.

function solve(tickets) {
  // 1. Group the tickets: for each airport, list where its tickets go
  const adj = new Map();
  for (const [a, b] of tickets) {
    if (!adj.has(a)) adj.set(a, []);
    adj.get(a).push(b);
  }
  // 2. Sort each list in reverse, so the smallest code is at the end
  for (const a of adj.values()) a.sort().reverse();
  // 3. Start at JFK with a stack for the current path and an empty route
  const stack = ["JFK"],
    out = [];
  while (stack.length) {
    // 4. Look at the tickets still unused at the airport on top of the stack
    // at(-1) is the last item. An airport that no ticket leaves has no list,
    // so next is undefined, and ?. then gives undefined instead of an error.
    const next = adj.get(stack.at(-1));
    if (next?.length) {
      // 5. A ticket is left: use the smallest one and move to that airport
      stack.push(next.pop());
    } else {
      // 6. No ticket is left: move this airport from the stack to the route
      out.push(stack.pop());
    }
  }
  // 7. The route was written from the end backwards, so return it reversed
  return out.reverse();
}

function solve(tickets: string[][]): string[] {
  // 1. Group the tickets: for each airport, list where its tickets go
  const adj = new Map<string, string[]>();
  for (const [a, b] of tickets) {
    if (!adj.has(a)) adj.set(a, []);
    adj.get(a)!.push(b);
  }
  // 2. Sort each list in reverse, so the smallest code is at the end
  for (const a of adj.values()) a.sort().reverse();
  // 3. Start at JFK with a stack for the current path and an empty route
  const stack = ["JFK"],
    out: string[] = [];
  while (stack.length) {
    // 4. Look at the tickets still unused at the airport on top of the stack
    // at(-1) is the last item. An airport that no ticket leaves has no list,
    // so next is undefined, and ?. then gives undefined instead of an error.
    const next = adj.get(stack.at(-1)!);
    if (next?.length) {
      // 5. A ticket is left: use the smallest one and move to that airport
      stack.push(next.pop()!);
    } else {
      // 6. No ticket is left: move this airport from the stack to the route
      out.push(stack.pop()!);
    }
  }
  // 7. The route was written from the end backwards, so return it reversed
  return out.reverse();
}

def solve(tickets):
    # 1. Group the tickets: for each airport, list where its tickets go
    graph = {}
    for source, destination in tickets:
        if source not in graph:
            graph[source] = []
        graph[source].append(destination)
    # 2. Sort each list in reverse, so the smallest code is at the end
    for destinations in graph.values():
        destinations.sort(reverse=True)
    # 3. Start at JFK with a stack for the current path and an empty route
    stack = ["JFK"]
    route = []
    while stack:
        # 4. Look at the tickets still unused at the airport on top of the stack
        # An airport that no ticket leaves has no list, and get then gives None.
        remaining = graph.get(stack[-1])
        if remaining:
            # 5. A ticket is left: use the smallest one and move to that airport
            stack.append(remaining.pop())
        else:
            # 6. No ticket is left: move this airport from the stack to the route
            route.append(stack.pop())
    # 7. The route was written from the end backwards, so return it reversed
    return route[::-1]

Example 2, traced

Input
tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]

Output
["JFK","NRT","JFK","KUL"]

Why it works

An airport is written to the route only when every ticket leaving it has been used, so everything that follows it in the trip is written already. The first airport written is where the trip must end, and each later one goes in front of what follows it. Trying the smallest destination first puts smaller codes as early as a complete trip allows.

Time and space

Time O(E log E), extra space O(E). E is the number of tickets. Grouping reads each ticket once, and the walk pushes and pops one airport per ticket, plus JFK. Sorting the lists costs the most, about E log E steps: O(E log E) time. The lists, stack and route hold about E entries: O(E) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not write airports down as you land. Flying the smallest ticket first and recording each landing goes from JFK to KUL in example 2, gets stuck there, and returns [JFK, KUL] with two tickets unused.
• The lists are sorted in reverse because tickets are taken from the end. Sorted the usual way, the largest code goes first: tickets [JFK,A], [JFK,B], [A,JFK], [B,JFK] give JFK, B, JFK, A, JFK instead of JFK, A, JFK, B, JFK.
• An airport that no ticket leaves has no list. Reading its list without checking fails at KUL in example 2: Python raises a KeyError, and JavaScript throws an error when it reads the length of undefined.

Pattern

Graph traversal with a visited set. Builds on Clone Graph and Course Schedule.

Keep going