How do you solve Reconstruct Itinerary on LeetCode?

Reconstruct Itinerary (LeetCode #332) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Utilizing a graph structure allows for efficient traversal of the itinerary.

What is the time complexity of Reconstruct Itinerary?

The optimal solution for Reconstruct Itinerary runs in O(n log n) time and uses O(n) space. The time complexity is O(n log n) due to sorting the tickets, and the space complexity is O(n) for storing the graph.

What is the brute force solution for Reconstruct Itinerary?

The brute force approach for Reconstruct Itinerary is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible itineraries from the given tickets and then selecting the one that starts with 'JFK' and has the smallest lexical order. This is straightforward but inefficient due to the large number of permutations. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Reconstruct Itinerary?

Explain your thought process clearly; interviewers appreciate understanding your reasoning. Consider edge cases, such as multiple valid itineraries. Practice writing clean and efficient code to avoid unnecessary complexity.

What are common mistakes when solving Reconstruct Itinerary?

Failing to account for all tickets being used exactly once. Not considering lexical order when constructing the itinerary.

#332

Reconstruct Itinerary

Hard

ArrayStringDepth-First SearchGraph TheorySortingHeap (Priority Queue)Eulerian CircuitHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal approach uses a graph representation of the tickets and a depth-first search (DFS) to construct the itinerary. By using a priority queue, we can ensure that we always explore the smallest lexical option first, leading to an efficient solution.

⚙️

Algorithm

3 steps

1Step 1: Build a graph where each airport points to a list of destinations sorted in lexical order.
2Step 2: Use DFS starting from 'JFK' to visit each airport, marking tickets as used.
3Step 3: Backtrack when necessary, ensuring all tickets are used exactly once.

solution.py15 lines

1from collections import defaultdict
2
3def findItinerary(tickets):
4    graph = defaultdict(list)
5    for src, dst in sorted(tickets):
6        graph[src].append(dst)
7    itinerary = []
8
9    def dfs(airport):
10        while graph[airport]:
11            dfs(graph[airport].pop(0))
12        itinerary.append(airport)
13
14    dfs('JFK')
15    return itinerary[::-1]

ℹ

Complexity note: The time complexity is O(n log n) due to sorting the tickets, and the space complexity is O(n) for storing the graph.

1Utilizing a graph structure allows for efficient traversal of the itinerary.
2Sorting the destinations ensures we always explore the smallest lexical option first.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.