Reconstruct Itinerary

Problem Description

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK". Thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexicographical order when read as a single string.

• For example, the itinerary ["JFK", "LGA"] has a smaller lexicographical order than ["JFK", "LGB"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Examples

Constraints

• 1 ≤ tickets.length ≤ 300
• tickets[i].length == 2
• fromi.length == 3, toi.length == 3
• fromi and toi consist of uppercase English letters.

Hierholzer’s Algorithm (Eulerian Path)

The problem asks us to find a path that uses every edge (flight ticket) exactly once. This is the definition of an Eulerian Path on a directed graph.

To construct the itinerary in lexicographical order:

1. Build an adjacency list where each airport points to a min-priority queue of destination airports (so we always try lexicographically smaller destinations first).
2. Perform a post-order depth-first search (DFS) starting from "JFK".
3. In the DFS:
   • While the current airport has outgoing flights, pop the smallest destination and recursively call DFS on it.
   • When the current airport has no outgoing flights left, append it to the itinerary result list.
4. The result list will hold the path in reverse order. Reverse it at the end to get the correct itinerary.

Why does this work? Airports with no outgoing edges (or whose edges have all been consumed) are pushed to the path first. Because they must be the end of the itinerary (or sub-loops), this correctly handles dead ends and loop-de-loops.

Solution: Hierholzer’s Eulerian Path DFS

import java.util.*;

class Solution {
    private Map<String, PriorityQueue<String>> adj = new HashMap<>();
    private List<String> itinerary = new ArrayList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            adj.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>()).offer(ticket.get(1));
        }

        dfs("JFK");
        Collections.reverse(itinerary);
        return itinerary;
    }

    private void dfs(String airport) {
        PriorityQueue<String> destinations = adj.get(airport);
        while (destinations != null && !destinations.isEmpty()) {
            String next = destinations.poll(); // consumes the ticket
            dfs(next);
        }
        itinerary.add(airport); // add when all outgoing tickets are consumed
    }
}

from collections import defaultdict
import heapq

class Solution:
    def findItinerary(self, tickets: list[list[str]]) -> list[str]:
        adj = defaultdict(list)
        for src, dest in tickets:
            adj[src].append(dest)

        # sort destinations so we can pop the smallest lexicographically
        for src in adj:
            adj[src].sort(reverse=True)  # reverse so we can pop from end in O(1)

        itinerary = []

        def dfs(airport: str):
            destinations = adj[airport]
            while destinations:
                next_airport = destinations.pop()
                dfs(next_airport)
            itinerary.append(airport)

        dfs("JFK")
        return itinerary[::-1]

#include <vector>
#include <string>
#include <unordered_map>
#include <queue>
#include <algorithm>

class Solution {
    std::unordered_map<std::string, std::priority_queue<std::string,
                       std::vector<std::string>, std::greater<std::string>>> adj;
    std::vector<std::string> itinerary;

    void dfs(const std::string& airport) {
        auto& dests = adj[airport];
        while (!dests.empty()) {
            std::string next = dests.top();
            dests.pop();
            dfs(next);
        }
        itinerary.push_back(airport);
    }

public:
    std::vector<std::string> findItinerary(std::vector<std::vector<std::string>>& tickets) {
        for (const auto& ticket : tickets) {
            adj[ticket[0]].push(ticket[1]);
        }

        dfs("JFK");
        std::reverse(itinerary.begin(), itinerary.end());
        return itinerary;
    }
};

Complexity Analysis:

• Time Complexity: O(E log E) where E is the number of tickets. Sorting/priority-queue operations for each edge take logarithmic time.
• Space Complexity: O(V + E) to store the graph.

← All Problems