Code Implementation

from collections import defaultdict
import heapq

class Solution:
    def findItinerary(self, tickets):
        graph = defaultdict(list)
        for src, dst in tickets:
            heapq.heappush(graph[src], dst)
        route = []
        def visit(airport):
            while graph[airport]:
                visit(heapq.heappop(graph[airport]))
            route.append(airport)
        visit("JFK")
        return route[::-1]
      

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, priority_queue<string, vector<string>, greater<string>>> graph;
        for (auto& t : tickets) {
            graph[t[0]].push(t[1]);
        }
        vector<string> route;
        function<void(string)> visit = [&](string airport) {
            while (!graph[airport].empty()) {
                string next = graph[airport].top();
                graph[airport].pop();
                visit(next);
            }
            route.push_back(airport);
        };
        visit("JFK");
        reverse(route.begin(), route.end());
        return route;
    }
};
      

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for (List<String> t : tickets) {
            graph.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).add(t.get(1));
        }
        List<String> route = new LinkedList<>();
        dfs("JFK", graph, route);
        return route;
    }

    private void dfs(String airport, Map<String, PriorityQueue<String>> graph, List<String> route) {
        PriorityQueue<String> dests = graph.get(airport);
        while (dests != null && !dests.isEmpty()) {
            dfs(dests.poll(), graph, route);
        }
        route.add(0, airport);
    }
}
      

var findItinerary = function(tickets) {
    const graph = {};
    for (const [from, to] of tickets) {
        if (!graph[from]) graph[from] = [];
        graph[from].push(to);
    }
    for (const node in graph) {
        graph[node].sort();
    }
    const route = [];
    function visit(airport) {
        const dests = graph[airport];
        while (dests && dests.length) {
            visit(dests.shift());
        }
        route.push(airport);
    }
    visit("JFK");
    return route.reverse();
};
      

Problem Description

You are given a list of airline tickets represented by pairs of departure and arrival airports, tickets, where each ticket is a two-element list [from, to]. You must reconstruct the itinerary in order, starting from "JFK" airport. The itinerary must use all the tickets exactly once and should be the lexicographically smallest itinerary if multiple valid answers exist.

• All tickets form at least one valid itinerary.
• You must use each ticket exactly once (no ticket re-use).
• Return the itinerary as a list of airport codes.
• If multiple valid itineraries exist, return the one with the smallest lexical order when read as a single string.

Thought Process

At first glance, this problem looks like a path-finding or permutation problem: we need to arrange the tickets in a sequence so that each connects to the next, starting at "JFK", and uses every ticket exactly once. A brute-force approach might try all possible orderings, but this is infeasible for large input sizes.

The requirement to use each ticket once is reminiscent of an Eulerian path in a directed graph, where each edge (ticket) is traversed exactly once. Additionally, the lexicographical order requirement means that if there are multiple choices, we should always pick the smallest next destination.

We need a way to efficiently traverse the tickets, always picking the lexicographically smallest option, and ensure all tickets are used. This leads us to consider a modified Hierholzer's algorithm for finding Eulerian paths, with the added twist of sorting destinations.

Solution Approach

• 1. Model the tickets as a graph:
  • Each airport is a node.
  • Each ticket is a directed edge from from to to.
• 2. Use a priority queue (min-heap) or sorted list for destinations:
  • This ensures the next destination is always the lexicographically smallest.
• 3. Traverse the graph using DFS (Depth-First Search):
  • At each airport, always visit the smallest next destination.
  • Remove the ticket as you use it (so it's not reused).
• 4. Build the itinerary in reverse:
  • When you reach an airport with no outgoing tickets, add it to the itinerary.
  • Backtrack, adding airports as you finish exploring all their outgoing edges.
  • Reverse the result at the end to get the correct order.
• 5. Return the final itinerary:
  • This will be the lexicographically smallest valid itinerary using all tickets.

We use a hash map for the adjacency list because lookups and insertions are O(1). A min-heap or sorted list ensures we always choose the next smallest destination efficiently.

Example Walkthrough

Input: [["MUC","LHR"], ["JFK","MUC"], ["SFO","SJC"], ["LHR","SFO"]]

1. Build the graph:
   • JFK: [MUC]
   • MUC: [LHR]
   • LHR: [SFO]
   • SFO: [SJC]
2. Start DFS from "JFK":
   • Go to MUC (only option from JFK).
   • From MUC, go to LHR.
   • From LHR, go to SFO.
   • From SFO, go to SJC.
   • SJC has no outgoing edges, add to itinerary.
   • Backtrack: add SFO, then LHR, then MUC, then JFK.
3. Reverse the itinerary: ["JFK", "MUC", "LHR", "SFO", "SJC"].

At each step, only one option exists, so the traversal is straightforward. If multiple destinations existed, the min-heap or sorted list ensures the lexicographically smallest is chosen.

Time and Space Complexity

• Brute-force approach:
  • Would try all possible permutations of tickets, leading to O(n!) time complexity, which is infeasible for large n.
• Optimized approach (Hierholzer’s Algorithm with min-heaps):
  • Time Complexity: O(E log E), where E is the number of tickets.
    • Building the graph: O(E log E) if we sort the destinations, or O(E log D) if using heaps (D = max number of destinations from an airport).
    • DFS traversal: O(E).
  • Space Complexity: O(E), for the graph and the recursion stack.

The optimized solution is efficient and scalable for the problem constraints.

Summary

By modeling the tickets as a directed graph and using a DFS traversal with a priority queue or sorted list for destinations, we can reconstruct the required itinerary efficiently. The key insight is to always pick the lexicographically smallest next airport, which is handled neatly by a min-heap or sorting. The solution leverages the structure of Eulerian paths and ensures each ticket is used exactly once, resulting in an elegant and optimal approach to the problem.