Reconstruct Itinerary

Examples

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

There's only one way to use every ticket starting from JFK.

Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]

Two different itineraries use every ticket exactly once - this one, and ["JFK","SFO","ATL","JFK","ATL","SFO"]. Comparing them stop by stop, the second stop is "ATL" vs "SFO", and "ATL" is alphabetically smaller, so the itinerary starting "JFK","ATL",... is preferred.

Constraints

• 1 <= tickets.length <= 300

• tickets[i].length == 2

• All airport codes are three uppercase English letters.

• You may assume every itinerary uses all the tickets and forms at least one valid route.

Approach

Every ticket is a directed edge from one airport to another, and using each ticket exactly once means walking every edge in this graph exactly once - the classic Eulerian path problem. The input guarantees such a path exists starting from "JFK".

A naive greedy DFS - always fly to the alphabetically smallest reachable airport - produces the lexically smallest route among valid options, but can dead-end early: you might use up a ticket that strands you at an airport with unused tickets you can no longer reach.

The reliable fix is Hierholzer's algorithm: do the same greedy DFS, but instead of recording an airport the moment you visit it, only record it once you've fully explored (used up) all of its outgoing tickets, and prepend it to the result. Any airport that turns out to be a dead end simply gets recorded (prepended) immediately, and the route naturally reroutes around it once you unwind the recursion - because the airport that led into that dead end still has other tickets left to try, and those get explored (and prepended) afterward, ending up later in the final order than the dead-end branch. Working through a few small examples by hand makes this "record on exit, prepend" trick click.

Solutions

Brute Force - Try Every Ticket Order

Since there are at most a few hundred tickets, one very naive approach is to treat this as choosing a permutation of the tickets to use one at a time: at each airport, try every unused ticket departing from it (in alphabetical order of destination, so the first complete route you find is already the lexically smallest one), recurse, and backtrack if a choice leads to a dead end before every ticket is used. This explores the same search space as a real DFS/backtracking solution but makes the backtracking explicit and returns as soon as one complete route is found.

function findItinerary(tickets) {
  const routesFrom = new Map();
  for (const [from, to] of tickets) {
    if (!routesFrom.has(from)) routesFrom.set(from, []);
    routesFrom.get(from).push(to);
  }
  for (const destinations of routesFrom.values()) {
    destinations.sort();
  }

  const used = new Array(tickets.length).fill(false);
  const route = ["JFK"];

  function backtrack(current) {
    if (route.length === tickets.length + 1) return true;

    const destinations = routesFrom.get(current) || [];
    for (let i = 0; i < destinations.length; i++) {
      // Find some unused ticket from "current" to destinations[i] - this
      // re-scans the whole ticket list on every step, which is what
      // makes this the brute force version rather than the optimal one.
      let ticketIndex = -1;
      for (let j = 0; j < tickets.length; j++) {
        if (tickets[j][0] === current && tickets[j][1] === destinations[i] && !used[j]) {
          ticketIndex = j;
          break;
        }
      }
      if (ticketIndex === -1) continue;

      used[ticketIndex] = true;
      route.push(destinations[i]);

      if (backtrack(destinations[i])) return true;

      route.pop();
      used[ticketIndex] = false;
    }
    return false;
  }

  backtrack("JFK");
  return route;
}

Time: O(E^2) in the worst case, where E is the number of tickets, since each of the E steps may re-scan and backtrack across the ticket list · Space: O(E) for the recursion stack, the route, and the used-ticket tracking

Optimal - Hierholzer's Algorithm

Group tickets by departure airport, sorting each airport's destinations alphabetically so the smallest option is tried first. Then run a DFS that, at each airport, repeatedly removes and follows the smallest remaining destination until that airport has no destinations left.

The key trick: only push an airport onto the result once its DFS call is about to return (meaning every outgoing ticket from it has been used). Because destinations are removed from the front of a sorted list as they're used, an airport that turns out to be a dead end gets pushed immediately, while the airport that led into it keeps exploring its remaining tickets and gets pushed only afterward - later in recursion, so it ends up appearing before the dead-end branch once you reverse the pushes at the end. Reversing the final list gives the route in the correct forward order.

function findItinerary(tickets) {
  const routesFrom = new Map();
  for (const [from, to] of tickets) {
    if (!routesFrom.has(from)) routesFrom.set(from, []);
    routesFrom.get(from).push(to);
  }
  for (const destinations of routesFrom.values()) {
    // Sort descending so the alphabetically smallest destination can
    // be removed cheaply from the end of the array.
    destinations.sort().reverse();
  }

  const route = [];

  function visit(airport) {
    const destinations = routesFrom.get(airport);
    while (destinations && destinations.length > 0) {
      const next = destinations.pop();
      visit(next);
    }
    route.push(airport);
  }

  visit("JFK");
  return route.reverse();
}

Time: O(E log E) for sorting each airport's destination list, then O(E) for the traversal itself, where E is the number of tickets · Space: O(E) to store the routes-by-airport map and the recursion stack