Reconstruct Itinerary

Q: What is the time complexity of Reconstruct Itinerary?

O(E!) in the worst case. Backtracking explores permutations of edges, but sorting and pruning reduce the search space significantly. The worst case is factorial in the number of tickets due to permutations, but pruning stops early once a valid path is found.

Q: What pattern does Reconstruct Itinerary use?

The Pattern: Backtracking (State Restoration with Lexicographical Ordering) The Heuristic: When searching for a path that must use all edges exactly once with lexicographical constraints, use backtracking that tries edges in sorted order, removing edges as they are used and restoring them upon backtracking to maintain correct state and enable pruning.

Medium Backtracking

Problem

Given a list of airline tickets represented as pairs of departure and arrival airports [from, to], reconstruct the itinerary in order such that all tickets are used exactly once and the itinerary starts from 'JFK'. If multiple valid itineraries exist, return the itinerary that is lexicographically smallest.

1 ≤ tickets.length ≤ 300
tickets[i].length == 2
from_i.length == 3
to_i.length == 3
from_i and to_i consist of uppercase English letters.

Example

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

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

Starting from 'JFK', the algorithm explores destinations in lexicographical order. It first chooses 'MUC' from 'JFK', then 'LHR' from 'MUC', followed by 'SFO' from 'LHR', and finally 'SJC' from 'SFO'. This path uses all tickets exactly once and is lexicographically smallest.

Approach

Straightforward Solution

A brute-force approach tries all permutations of tickets to find a valid itinerary, which is factorial in time and infeasible for large inputs.

Core Observation

The problem requires finding a path that uses all edges (tickets) exactly once in a directed graph, starting from a fixed node 'JFK'. This is a classic Eulerian path problem with the added constraint of lexicographical order.

Path to Optimal

Preview

Recognizing the problem as finding an Eulerian path allows the use of Hierholzer's algorithm or backtracking with pruning. Sorting the adjacency lists lexicographically ensures the lexicographically smallest path is found first…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build an adjacency list mapping each source to a lexicographically sorted list of destinations. Use backtracking starting from 'JFK', at each step choosing the next lexicographically smallest destination, removing the edge from the adjacency list, and recursively continuing…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(E!) in the worst case

Backtracking explores permutations of edges, but sorting and pruning reduce the search space significantly. The worst case is factorial in the number of tickets due to permutations, but pruning stops early once a valid path is found.

Space

O(V + E)

The adjacency list stores all edges, and recursion stack can go as deep as the number of tickets (edges). Auxiliary space is proportional to vertices and edges.

Pattern Spotlight

Backtracking (State Restoration with Lexicographical Ordering)

When searching for a path that must use all edges exactly once with lexicographical constraints, use backtracking that tries edges in sorted order, removing edges as they are used and restoring them upon backtracking to maintain correct state and enable pruning.

Solution

Python

1import collections
2
3class Solution:
  def findItinerary(self, 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

Step-by-Step Solution

Build Lexicographically Sorted Adjacency List

5adj = {src: [] for src, dst in tickets}
6tickets.sort()
7for src, dst in tickets:
8    adj[src].append(dst)

Objective

To construct a graph representation where each source airport maps to a sorted list of destination airports, enabling lexicographical traversal.

Key Insight

Sorting the tickets before building the adjacency list ensures that destinations are appended in lexicographical order. This ordering is critical because the backtracking algorithm relies on exploring edges in sorted order to find the lexicographically smallest itinerary first.

Interview Quick-Check

Core Logic

Sorting tickets upfront guarantees adjacency lists are lexicographically ordered, enabling efficient backtracking without additional sorting.

Common Pitfalls & Bugs

Failing to sort the tickets or adjacency lists can lead to incorrect or non-lexicographically minimal itineraries.

Initialize Result and Define Backtracking DFS

To prepare the result list starting from 'JFK' and define a recursive DFS function that attempts to build a valid itinerary using all tickets.

Explore Next Destinations with Backtracking and State Restoration

To recursively try each possible next destination from the current airport, removing the edge to prevent reuse and restoring it if the path does not lead to a solution.

Invoke DFS from 'JFK' and Return Final Itinerary

To start the backtracking search from 'JFK' and return the constructed itinerary after successful completion.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 19 Critical

adj[src].pop(i)

Remove the destination from the original adjacency list to mark the ticket as used.

Removing the edge prevents reuse of the same ticket, ensuring each ticket is used exactly once in the itinerary.

Line 23 Critical

adj[src].insert(i, v)

Restore the removed destination to the adjacency list upon backtracking.

Restoring the edge allows alternative paths to be explored, maintaining correct state for backtracking.

Line 24 Critical

res.pop()

Remove the last added destination from the itinerary to backtrack.

Removing the last airport restores the path state, enabling exploration of other possible itineraries.

Full line-by-line criticality + rationale for all 21 lines available on Pro.

Test Your Understanding

Why must edges be removed from the adjacency list when used and restored upon backtracking?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Reconstruct Itinerary from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Reconstruct Itinerary drill

or drill a free problem

1	`import collections`
2
3	`class Solution:`
4	`def findItinerary(self, tickets: list[list[str]]) -> list[str]:`
5	`adj = {src: [] for src, dst in tickets}`
6	`tickets.sort()`
7	`for src, dst in tickets:`
8	`adj[src].append(dst)`
9
10	`res = ["JFK"]`
11	`def dfs(src):`
12	`if len(res) == len(tickets) + 1:`
13	`return True`
14	`if src not in adj:`
15	`return False`
16
17	`temp = list(adj[src])`
18	`for i, v in enumerate(temp):`
19	`adj[src].pop(i)`
20	`res.append(v)`
21	`if dfs(v):`
22	`return True`
23	`adj[src].insert(i, v)`
24	`res.pop()`
25	`return False`
26
27	`dfs("JFK")`
28	`return res`

5	`adj = {src: [] for src, dst in tickets}`
6	`tickets.sort()`
7	`for src, dst in tickets:`
8	`adj[src].append(dst)`