Reconstruct Itinerary

You have a stack of plane tickets. Each ticket takes you from one airport to another. You must use every single ticket exactly once and end up with one full trip. This question looks like a simple path search. But the trick is you cannot get stuck. So you need a clever order. That is what makes Reconstruct Itinerary a favorite in interviews.

🎯 The Problem

You get a list of plane tickets and must build one trip that uses every ticket.

• Each ticket is a pair [from, to]. It is a one-way flight.
• You must use every ticket exactly once.
• The trip always starts from the airport "JFK".
• If many valid trips exist, return the one that is smallest in lexical order.
• Lexical order means you compare names letter by letter, like words in a dictionary. So "ATL" comes before "SFO".

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

Explanation: Start at JFK. This order uses every ticket once.
Another valid path exists, but this one is the smallest in dictionary order.

This is really an Eulerian path question. An Eulerian path is a walk through a graph that uses every edge exactly once. Here each airport is a node and each ticket is a one-way edge.

Here is the graph for the example. Each arrow is one ticket you must use.

🐢 Approach 1: Backtracking (Brute Force)

We try every order and undo the bad ones.

The idea:

• Start at "JFK". Pick any ticket leaving the current airport. Fly there.
• Keep going. If you hit a dead end before all tickets are used, back up and try another ticket.
• Backtracking means you try a path, and if it fails you undo the last step and try another.

How it works:

• Always try the destinations in sorted order first. That gives the smallest trip.
• Stop the moment you find a full trip that used every ticket.

Why it is weak:

• The number of orders can explode with many tickets.
• The same bad choices get tried again and again.
• The time can grow far faster than the input.

Here is the backtracking code:

def find_itinerary(tickets):
    tickets.sort()
    used = [False] * len(tickets)
    path = ["JFK"]
    def dfs():
        if len(path) == len(tickets) + 1: return True
        for i, (src, dst) in enumerate(tickets):
            if not used[i] and src == path[-1]:
                used[i] = True; path.append(dst)
                if dfs(): return True
                path.pop(); used[i] = False
        return False
    dfs(); return path

⚡ Approach 2: Hierholzer’s Algorithm (Best)

The idea in one line: walk forward greedily, and only record an airport once you can go no further from it.

The idea:

• This is Hierholzer’s algorithm, built exactly for Eulerian paths.
• Sort the destinations from each airport, smallest name first.
• Always leave toward the smallest airport you still have a ticket for. That keeps the trip lexically smallest.

How it works:

• Do a depth-first walk. Depth-first means keep going deeper down one path before trying others.
• Keep flying out of the current airport, removing each used ticket, until it has no tickets left.
• When an airport is stuck, add it to the front of the answer.
• Then back up and finish the rest.

Why adding to the front works:

• The airport that gets stuck first is really the last stop of the trip.
• Adding stuck airports to the front makes the final list read in correct travel order.
• You can reverse at the end, or insert at the front as you go.

Why it is fast:

• Each ticket is used exactly once.
• Sorting the destinations adds only a log factor.

Here is the depth-first walk on the example. We always leave toward the smallest airport. Each step uses one ticket.

Steps to Solve

1. Build a map from each airport to a sorted list of its destinations.
2. Start a depth-first walk from "JFK".
3. From the current airport, always fly to the smallest unused destination first. Remove that ticket.
4. Keep going until the current airport has no destinations left.
5. When an airport is stuck, add it to the front of the route.
6. After the walk finishes, the route holds the full journey in order.

#include <stdio.h>
#include <string.h>

#define MAXT 100

char from[MAXT][4];
char to[MAXT][4];
int used[MAXT];
int n;

char route[MAXT + 1][4];
int routeLen = 0;

// pick the smallest unused destination from 'airport' each time
void visit(const char *airport) {
    while (1) {
        int best = -1;
        for (int i = 0; i < n; i++) {
            if (!used[i] && strcmp(from[i], airport) == 0) {
                if (best == -1 || strcmp(to[i], to[best]) < 0) {
                    best = i;  // smallest destination by name
                }
            }
        }
        if (best == -1) break;   // no tickets left here
        used[best] = 1;
        visit(to[best]);
    }
    // airport is stuck, record it
    strcpy(route[routeLen++], airport);
}

int main(void) {
    const char *t[][2] = {
        {"JFK","SFO"}, {"JFK","ATL"}, {"SFO","ATL"},
        {"ATL","JFK"}, {"ATL","SFO"}
    };
    n = 5;
    for (int i = 0; i < n; i++) {
        strcpy(from[i], t[i][0]);
        strcpy(to[i], t[i][1]);
        used[i] = 0;
    }
    visit("JFK");

    // route is filled in reverse, so print from the end
    printf("[");
    for (int i = routeLen - 1; i >= 0; i--) {
        printf("\"%s\"", route[i]);
        if (i > 0) printf(",");
    }
    printf("]\n");
    return 0;
}

["JFK","ATL","JFK","SFO","ATL","SFO"]

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;

map<string, multiset<string>> graph;  // airport -> sorted destinations
vector<string> route;

void visit(const string &airport) {
    auto &dests = graph[airport];
    while (!dests.empty()) {
        string next = *dests.begin();  // smallest destination
        dests.erase(dests.begin());    // use this ticket
        visit(next);
    }
    route.push_back(airport);  // stuck, record it
}

int main() {
    vector<pair<string,string>> tickets = {
        {"JFK","SFO"}, {"JFK","ATL"}, {"SFO","ATL"},
        {"ATL","JFK"}, {"ATL","SFO"}
    };
    for (auto &t : tickets) graph[t.first].insert(t.second);

    visit("JFK");

    cout << "[";
    for (int i = (int)route.size() - 1; i >= 0; i--) {
        cout << "\"" << route[i] << "\"";
        if (i > 0) cout << ",";
    }
    cout << "]" << endl;
    return 0;
}

["JFK","ATL","JFK","SFO","ATL","SFO"]

import java.util.*;

public class Itinerary {
    static Map<String, PriorityQueue<String>> graph = new HashMap<>();
    static LinkedList<String> route = new LinkedList<>();

    static void visit(String airport) {
        PriorityQueue<String> dests = graph.get(airport);
        while (dests != null && !dests.isEmpty()) {
            String next = dests.poll();  // smallest destination
            visit(next);
        }
        route.addFirst(airport);  // stuck, add to the front
    }

    public static void main(String[] args) {
        String[][] tickets = {
            {"JFK","SFO"}, {"JFK","ATL"}, {"SFO","ATL"},
            {"ATL","JFK"}, {"ATL","SFO"}
        };
        for (String[] t : tickets) {
            graph.computeIfAbsent(t[0], k -> new PriorityQueue<>()).add(t[1]);
        }
        visit("JFK");

        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < route.size(); i++) {
            sb.append("\"").append(route.get(i)).append("\"");
            if (i < route.size() - 1) sb.append(",");
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

["JFK","ATL","JFK","SFO","ATL","SFO"]

from collections import defaultdict

def find_itinerary(tickets):
    graph = defaultdict(list)
    # sort destinations in reverse so we can pop the smallest from the end
    for src, dst in sorted(tickets, reverse=True):
        graph[src].append(dst)

    route = []

    def visit(airport):
        while graph[airport]:
            next_stop = graph[airport].pop()  # smallest destination
            visit(next_stop)
        route.append(airport)                 # stuck, record it

    visit("JFK")
    return route[::-1]                         # reverse to travel order


tickets = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"],
           ["ATL", "JFK"], ["ATL", "SFO"]]
print(find_itinerary(tickets))

['JFK', 'ATL', 'JFK', 'SFO', 'ATL', 'SFO']

function findItinerary(tickets) {
  const graph = {};
  // sort so the smallest destination sits at the end of the array
  for (const [src, dst] of tickets.sort().reverse()) {
    if (!graph[src]) graph[src] = [];
    graph[src].push(dst);
  }

  const route = [];

  function visit(airport) {
    const dests = graph[airport] || [];
    while (dests.length > 0) {
      const next = dests.pop(); // smallest destination
      visit(next);
    }
    route.push(airport); // stuck, record it
  }

  visit("JFK");
  return route.reverse(); // travel order
}

const tickets = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"],
                 ["ATL", "JFK"], ["ATL", "SFO"]];
console.log(findItinerary(tickets));

[ 'JFK', 'ATL', 'JFK', 'SFO', 'ATL', 'SFO' ]

Let us walk through the Python version line by line and see why each part is there.

for src, dst in sorted(tickets, reverse=True):
    graph[src].append(dst)

We sort the tickets in reverse and append each destination. So inside each airport’s list, the largest name sits at the front and the smallest sits at the end. We want the smallest first, and popping from the end of a Python list is fast. So a reverse sort lets us pop the smallest cheaply.

def visit(airport):
    while graph[airport]:
        next_stop = graph[airport].pop()
        visit(next_stop)
    route.append(airport)

This is the heart of Hierholzer’s algorithm. The while keeps flying out of the current airport as long as it has tickets. pop() takes the smallest remaining destination and removes that ticket so we never reuse it. Then we recurse into that next airport. When the loop ends, the airport has no tickets left. So it is stuck. We append it to route.

return route[::-1]

The stuck airports were added in reverse travel order. The first airport we got stuck at is really the end of the trip. So we reverse the whole list to read it as a real journey from start to finish.

⏱️ Time and Space Complexity

Let E be the number of tickets, which are the edges. The brute force tries many orders, so its time can grow much faster than the input. Hierholzer’s algorithm touches each ticket once. The sorting of destinations adds a log factor. So the total time is about O(E log E). The space holds the graph and the recursion, which is O(E).

🧩 Key Takeaways

• ✅ This is an Eulerian path problem, which means using every edge exactly once.
• ✅ Hierholzer’s algorithm walks greedily and records an airport only when it gets stuck.
• ✅ Always fly to the smallest destination first to get the lexical-order journey.
• ✅ Add stuck airports to the front, then the route reads in correct order.
• ✅ It runs in O(E log E) time because each ticket is used once and destinations are sorted.

🚀 What’s Next?

• Network Delay Time
• Alien Dictionary