Here is solutions for Reconstruct Flight Path.

1. Understand the problem

• You are given a list of airline tickets where:

tickets[i] = [from, to]

• You must:

  • Start the trip from “JFK”

  • Use all tickets exactly once

  • Return the lexicographically smallest valid itinerary

  • Each ticket is a directed edge

  • The itinerary is a path that uses every edge exactly once

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. Are we guaranteed that a valid itinerary always exists?

• ✅ Yes.

1. Can there be duplicate tickets?

• ✅ Yes (same from → to multiple times).

1. Is the graph guaranteed to be connected from JFK?

• ✅ Yes, otherwise no valid solution.

1. How large is tickets?

• Typical: up to 10⁴–10⁵, so need O(n log n) or better.

1. If multiple valid itineraries exist, how to choose?

• ✅ Return lexicographically smallest.

3. Explore examples.

1. Example 1

tickets = [
  ["MUC","LHR"],
  ["JFK","MUC"],
  ["SFO","SJC"],
  ["LHR","SFO"]
]

Graph: JFK → MUC → LHR → SFO → SJC

1. Example 2

tickets = [
  ["JFK","KUL"],
  ["JFK","NRT"],
  ["NRT","JFK"]
]

Two choices from JFK: KUL, NRT
Lexicographically smaller = KUL, but that leads to dead end ❌

=> Graph: ["JFK","NRT","JFK","KUL"]

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1: Naive Backtracking (Brute Force) - Time O(N!), Space O(N!)

• Idea:

  • Try all possible permutations of paths

  • Track used tickets

  • Choose the smallest valid result

• Time: O(N!).

• Space O(N!)

4.2. Solution 2: DFS with Sorting + Backtracking - Time O(E * V), Space O(E * V)

• Idea:

  • Build adjacency list

  • Sort neighbors

  • DFS and mark tickets as used

• Time: O(E * V), due to reverse the repeated edge of the graph in the path.

• Space: O(E * V).

4.3. Solution 3: Hierholzer’s Algorithm (Correct & Optimal)

• Key Idea:

  • Each ticket = directed edge

  • We need an Eulerian Path

  • Always take the smallest lex destination first

  • When stuck, backtrack and add airport to result

  • Reverse the result at the end

=> This is must be the end of the graph.

• Time: O(ElogE).

• Space: O(E)

5. Implement solutions.

5.1. Naive DFS - Time (E * V), Space O (E * V)

from collections import defaultdict

class Solution:
    def findItinerary(self, tickets):
        # 1. Build graph: src -> list of (dst, ticket_index)
        graph = defaultdict(list)
        for i, (src, dst) in enumerate(tickets):
            graph[src].append((dst, i))

        # 2. Sort each adjacency list lexicographically by destination
        for src in graph:
            graph[src].sort()

        used = [False] * len(tickets)
        path = ["JFK"]

        # 3. Naive DFS with backtracking
        def dfs(curr):
            if len(path) == len(tickets) + 1:
                return True  # found full valid itinerary

            for next_airport, idx in graph[curr]:
                if not used[idx]:
                    used[idx] = True
                    path.append(next_airport)

                    if dfs(next_airport):
                        return True  # stop at first valid lex path

                    # backtrack
                    used[idx] = False
                    path.pop()

            return False

        dfs("JFK")
        return path

• Time: O(E * V) => One DFS = O(E), Run V times, ✅ Total = O(V * E)

• Space: O(E * V)

5.2. Hierholzer’s Algorithm - Time O(E * logE), Space O(E)

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

        res = []
        def dfs(src):
            while adj[src]:
                dst = adj[src].pop()
                dfs(dst)
            res.append(src)

        dfs('JFK')
        return res[::-1]

• Time: O(E * logE) => Pop to the last and backtrack in adj[src], so it call O(E) recursion

• Space: O(E)

5.3. Hierholzer’s Algorithm - Time O(E * logE), Space O(E)

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

        stack = ["JFK"]
        res = []

        while stack:
            curr = stack[-1]
            if not adj[curr]:
                res.append(stack.pop())
            else:
                stack.append(adj[curr].pop())

        return res[::-1]

• Time: O(E * logE)

• Space: O(E)

6. Dry run testcases.

tickets = [
  ["JFK","KUL"],
  ["JFK","NRT"],
  ["NRT","JFK"]
]

=>

[
  ["JFK","KUL"],
  ["JFK","NRT"],
  ["NRT","JFK"]
]

=>

[
  ["NRT","JFK"],
  ["JFK","NRT"],
  ["JFK","KUL"]
]

=>

JFK → ["NRT", "KUL"]
NRT → ["JFK"]


res = ["KUL", "JFK", "NRT", "JFK"]

=> Reverse this.

• But res is NOT the path yet. It is the path in reverse finishing order.

Idea:

• Find the less destination first + no path vertices, about the dict but order lexicographically matter.

• Why you make sure JFK connect to KUL ?

  • Mental model: Every time we make a recursive call dfs(v) from dfs(u), the edge u → v corresponds to a real ticket and is permanently consumed before v is appended to res.