Reconstruct Flight Path

Problem Statement

You are given a list of flight tickets tickets where tickets[i] = [from_i, to_i] represent the source airport and the destination airport.

Each from_i and to_i consists of three uppercase English letters.

Reconstruct the itinerary in order and return it.

All of the tickets belong to someone who originally departed from "JFK". Your objective is to reconstruct the flight path that this person took, assuming each ticket was used exactly once.

If there are multiple valid flight paths, return the lexicographically smallest one.

  • For example, the itinerary ["JFK", "SEA"] has a smaller lexical order than ["JFK", "SFO"].

You may assume all the tickets form at least one valid flight path.

Example 1:

Input: tickets = [["BUF","HOU"],["HOU","SEA"],["JFK","BUF"]]


Output: ["JFK","BUF","HOU","SEA"]

Example 2:

Input: tickets = [["HOU","JFK"],["SEA","JFK"],["JFK","SEA"],["JFK","HOU"]]


Output: ["JFK","HOU","JFK","SEA","JFK"]

Explanation: Another possible reconstruction is ["JFK","SEA","JFK","HOU","JFK"] but it is lexicographically larger.

Constraints:

  • 1 <= tickets.length <= 300
  • from_i != to_i

You should aim for a solution with O(E \log E) time and O(E) space, where E is the number of tickets (edges).

You should aim for a solution with O(E \log E) time and O(E) space, where E is the number of tickets (edges).

Hint 1

Consider this problem as a graph where airports are the nodes and tickets are the edges. Since we need to utilize all the tickets exactly once, can you think of an algorithm that visits every edge exactly once? Additionally, how do you ensure the smallest lexical order is maintained?

Hint 2

We build an adjacency list from the given tickets, which represent directed edges. We perform a DFS to construct the result, but we first sort the neighbors’ list of each node to ensure the smallest lexical order. Why? Sorting guarantees that during DFS, we visit the node with the smallest lexical order first.

Hint 3

DFS would be a naive solution, as it takes O(E * V) time, where E is the number of tickets (edges) and V is the number of airports (nodes). In this approach, we traverse from the given source airport JFK, perform DFS by removing the neighbor, traversing it, and then reinserting it back. Can you think of a better way? Perhaps an advanced algorithm that incorporates DFS might be helpful?

Hint 4

We can use Hierholzer’s algorithm, a modified DFS approach. Instead of appending the node to the result list immediately, we first visit all its neighbors. This results in a post-order traversal. After completing all the DFS calls, we reverse the path to obtain the final path, which is also called Euler’s path.

Solution

def find_itinerary(tickets: list[list[str]]) -> list[str]:
    adj = {src: [] for src, dst in tickets}
    tickets.sort()
    for src, dst in tickets:
        adj[src].append(dst)


    res = ["JFK"]


    def dfs(src):
        if len(res) == len(tickets) + 1:
            return True
        if src not in adj:
            return False


        temp = list(adj[src])
        for i, v in enumerate(temp):
            adj[src].pop(i)
            res.append(v)
            if dfs(v):
                return True
            adj[src].insert(i, v)
            res.pop()
        return False


    dfs("JFK")
    return res

Time complexity: O(E * V) Space complexity: O(E * V)