LeetCode 332: Reconstruct Itinerary Solution in Python – A Step-by-Step Guide

What Is LeetCode 332: Reconstruct Itinerary?

In LeetCode 332: Reconstruct Itinerary, you’re given a list of flight tickets as pairs [from, to] and must reconstruct a valid itinerary starting from "JFK", using all tickets exactly once. If multiple valid itineraries exist, return the lexicographically smallest one. For example, with tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]], the itinerary is ["JFK","MUC","LHR","SFO","SJC"]. This problem tests your ability to navigate a directed graph, connecting to concepts in LeetCode 207: Course Schedule.

Problem Statement

• Input: A list of string pairs tickets (each pair is [from, to]).
• Output: A list of strings—the itinerary starting from "JFK".
• Rules:
• Use all tickets exactly once.
• Start at "JFK".
• Return lexicographically smallest if multiple solutions exist.

Constraints

• 1 <= tickets.length <= 300
• tickets[i].length == 2
• tickets[i][j] is a 3-letter airport code (uppercase).
• All tickets form at least one valid itinerary.

Examples

• Input: [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
• Output: ["JFK","MUC","LHR","SFO","SJC"]
• Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
• Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
• Input: [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
• Output: ["JFK","NRT","JFK","KUL"]

Understanding the Problem: Building the Itinerary

To solve LeetCode 332: Reconstruct Itinerary in Python, we need to construct a valid path through a directed graph (airports as nodes, tickets as edges) starting from "JFK", using all edges exactly once. This resembles an Eulerian path problem, and a naive approach—trying all permutations—is O(n!), impractical for 300 tickets. Instead, we’ll use:

• Best Solution (DFS with Hierholzer’s): O(n log n) time, O(n) space—fast and optimal.
• Alternative Solution (Backtracking): O(n!) time, O(n) space—intuitive but slow.

Let’s start with the DFS solution, explained in a beginner-friendly way.

Best Solution: DFS with Hierholzer’s Algorithm

Why This Is the Best Solution

The DFS with Hierholzer’s algorithm approach is the top choice for LeetCode 332 because it’s efficient—O(n log n) time, O(n) space—and leverages a graph traversal strategy to find an Eulerian path in one pass. It uses a priority queue to ensure lexicographically smallest destinations are chosen, building the itinerary in reverse. It’s like planning a trip by always picking the next best flight—smart and streamlined!

How It Works

Think of this as a flight scheduler:

• Step 1: Build Graph:
• Use a dictionary with priority queues (min-heap) for each airport’s destinations.
• Step 2: DFS from "JFK":
• Recursively visit each airport.
• Pop smallest destination, explore it, then add current airport to itinerary.
• Step 3: Reverse Result:
• DFS builds path backwards; reverse to get forward order.
• Step 4: Why It Works:
• Hierholzer’s ensures all edges are used (Eulerian path exists).
• Min-heap guarantees lexicographical order.

It’s like flying through the graph with a perfect plan!

Step-by-Step Example

Example: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

• Graph:
• JFK: [ATL, SFO]
• SFO: [ATL]
• ATL: [JFK, SFO]
• DFS("JFK"):
• Pop ATL: DFS("ATL")
• Pop JFK: DFS("JFK")
• Pop SFO: DFS("SFO")
• Pop ATL: DFS("ATL")
• Pop SFO: DFS("SFO")
• Empty, add "SFO"
• Add "ATL"
• Add "SFO"
• Add "JFK"
• Add "ATL"
• Add "JFK"
• Reverse: ["JFK","ATL","JFK","SFO","ATL","SFO"]
• Result: ["JFK","ATL","JFK","SFO","ATL","SFO"]

Code with Detailed Line-by-Line Explanation

Copy codefrom collections import defaultdict
import heapq

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        # Build graph with priority queues
        graph = defaultdict(list)
        for src, dst in tickets:
            heapq.heappush(graph[src], dst)

        # DFS to construct itinerary
        itinerary = []

        def dfs(airport):
            while graph[airport]:
                next_airport = heapq.heappop(graph[airport])
                dfs(next_airport)
            itinerary.append(airport)

        # Start from JFK
        dfs("JFK")
        return itinerary[::-1]  # Reverse to get correct order

• Lines 6-8: Build graph with min-heaps for lexicographical order.
• Lines 11-16: DFS:
• Pop smallest destination, recurse, then add current airport.
• Line 19: Start DFS from "JFK", reverse result.
• Time Complexity: O(n log n)—heap operations for n tickets.
• Space Complexity: O(n)—graph and itinerary storage.

This is like a flight-routing maestro—fast and precise!

Alternative Solution: Backtracking

Why an Alternative Approach?

The backtracking approach—O(n!) time, O(n) space—tries all possible paths, building the itinerary by exploring options and backtracking when stuck. It’s more intuitive for understanding path construction but impractical for large inputs. It’s like trying every flight combination—thorough but slow!

How It Works

Explore all paths:

• Step 1: Build adjacency list with ticket counts.
• Step 2: Backtrack from "JFK":
• Try each destination, recurse if valid, undo if stuck.
• Step 3: Stop at first valid path (lexicographical order via sorting).

Step-by-Step Example

Example: tickets = [["JFK","SFO"],["JFK","ATL"]]

• Graph: JFK: {SFO:1, ATL:1}
• Backtrack("JFK", 2):
• Try ATL: ["JFK","ATL"], remaining=1, no path
• Backtrack, try SFO: ["JFK","SFO"], remaining=1, no path
• Valid path found earlier: ["JFK","ATL"]
• Result: ["JFK","ATL"] (simplified, full example would continue)

Code for Backtracking Approach

Copy codefrom collections import defaultdict

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        # Build graph with ticket counts
        graph = defaultdict(lambda: defaultdict(int))
        for src, dst in tickets:
            graph[src][dst] += 1

        # Backtracking
        def backtrack(curr, remaining):
            if remaining == 0:
                return True
            for next_airport in sorted(graph[curr]):
                if graph[curr][next_airport] > 0:
                    graph[curr][next_airport] -= 1
                    itinerary.append(next_airport)
                    if backtrack(next_airport, remaining - 1):
                        return True
                    itinerary.pop()
                    graph[curr][next_airport] += 1
            return False

        itinerary = ["JFK"]
        backtrack("JFK", len(tickets))
        return itinerary

• Time Complexity: O(n!)—exponential due to backtracking.
• Space Complexity: O(n)—graph and recursion stack.

It’s a path-exploring traveler—vivid but heavy!

Comparing the Two Solutions

• DFS with Hierholzer’s (Best):
• Pros: O(n log n) time, O(n) space, efficient and guaranteed.
• Cons: Graph logic less intuitive.
• Backtracking (Alternative):
• Pros: O(n!) time, O(n) space, clear exploration.
• Cons: Too slow for large n.

DFS wins for performance.

Additional Examples and Edge Cases

• [["JFK","ATL"]]: ["JFK","ATL"].
• [["JFK","SFO"]]: ["JFK","SFO"].
• Complex cycles: Handled by DFS order.

Both work, but DFS is faster.

Complexity Breakdown

• DFS with Hierholzer’s: Time O(n log n), Space O(n).
• Backtracking: Time O(n!), Space O(n).

DFS is the clear choice.

Key Takeaways

• DFS with Hierholzer’s: Fly smart—efficient!
• Backtracking: Try all—simple!
• Python: Heaps and dicts shine—see [Python Basics](/python/basics).
• Graphs: Paths shape the journey.

Final Thoughts: Plan the Trip

LeetCode 332: Reconstruct Itinerary in Python is a graph-traversal adventure. The DFS with Hierholzer’s solution offers speed and elegance, while backtracking provides a tangible baseline. Want more graph challenges? Try LeetCode 207: Course Schedule or LeetCode 310: Minimum Height Trees. Ready to travel? Head to Solve LeetCode 332 on LeetCode and chart that itinerary today!