NUHMAN.com

Introduction

LeetCode 332: Reconstruct Itinerary is a problem that tests your ability to work with directed graphs and Eulerian paths. The problem provides a list of flights as pairs of departure and destination cities, and the task is to reconstruct the itinerary that visits every flight exactly once, starting from JFK.

This problem can be efficiently solved using Hierholzer’s algorithm for finding Eulerian paths in a directed graph.

Problem Statement

You are given a list of airline tickets represented by pairs of strings [from, to]. Reconstruct and return the itinerary that starts at JFK and uses all the tickets exactly once.

Note:

• You must visit each airport exactly once and you must follow the exact order of tickets.
• If there are multiple valid itineraries, return the lexicographically smallest one.

Example

python

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

Input: [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]
Output: ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]

✅ Approach: Hierholzer's Algorithm (Graph Traversal)

The idea is to treat the airports as nodes in a directed graph, and each flight as a directed edge. The task is to find an Eulerian path that visits every edge exactly once.

Steps:

1. Graph Construction: Use a hashmap (or dictionary) to store the adjacency list for the graph. For each node, store a min-heap (priority queue) to ensure the lexicographically smallest destination is visited first.
2. DFS Traversal: Start from JFK and use DFS (Depth First Search) to traverse the graph:

• If a node has outgoing flights, visit the next available destination.
• Once all flights from a node are used, backtrack and add the node to the itinerary.

1. Sorting the Destinations: Ensure that each node’s destinations are visited in lexicographical order by using a min-heap.

✅ Python Code

python

import heapq

class Solution:
    def findItinerary(self, tickets: list[list[str]]) -> list[str]:
        # Create a graph using a dictionary with a min-heap (priority queue)
        graph = {}
        for start, end in tickets:
            if start not in graph:
                graph[start] = []
            heapq.heappush(graph[start], end)

        itinerary = []
        
        # DFS helper function
        def dfs(airport):
            # If there are still destinations, visit the next one
            while airport in graph and graph[airport]:
                next_airport = heapq.heappop(graph[airport])
                dfs(next_airport)
            # Add the airport to the itinerary after all outgoing flights are used
            itinerary.append(airport)

        # Start DFS from 'JFK'
        dfs("JFK")
        
        # Since we're adding airports in reverse order, reverse the list before returning
        return itinerary[::-1]

🧪 Dry Run Example

Input: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"], ["JFK", "ATL"], ["ATL", "SFO"], ["SJC", "LHR"]]

1. Graph Construction:

• graph = {"JFK": ["ATL", "MUC"], "ATL": ["SFO"], "MUC": ["LHR"], "LHR": ["SFO"], "SFO": ["SJC"], "SJC": ["LHR"]}

1. DFS Traversal:

• Starting at JFK:
• Visit ATL, then from ATL, visit SFO, then from SFO, visit SJC, and finally from SJC, visit LHR.
• Backtrack to SFO, then visit LHR from LHR and finally MUC.

1. Result: ["JFK", "ATL", "SFO", "SJC", "LHR", "MUC"]

⏱️ Time & Space Complexity

MetricValueTime ComplexityO(E log V)Space ComplexityO(E + V)

• E is the number of flights (edges), and V is the number of airports (vertices).
• Sorting destinations using a heap ensures that the complexity remains efficient, especially when there are many airports with multiple destinations.

🧠 Key Takeaways

• Hierholzer's algorithm is useful for finding Eulerian paths in graphs.
• Using a min-heap ensures that we always visit the lexicographically smallest destination first, satisfying the problem's requirements.
• DFS allows us to backtrack and add nodes to the itinerary in reverse order.

🧱 Edge Cases

• No tickets → return []
• Multiple possible itineraries → return the lexicographically smallest one
• All flights from the same airport → ensure all tickets are used

✅ Conclusion

LeetCode 332: Reconstruct Itinerary challenges you to work with graphs and Eulerian paths, a crucial concept in graph theory. By using Hierholzer's algorithm and a min-heap, we efficiently build the desired itinerary, making this problem both an interesting and practical application of graph traversal.