LeetCode 332 - Reconstruct Itinerary

The problem is asking us to reconstruct a flight itinerary given a list of tickets. Each ticket is a one-way flight represented as a pair of airport codes [from, to]. The traveler always starts at "JFK", and the itinerary must use all tickets exactly once.

leetcodehardarraystringdepth-first-searchgraph-theorysortingheap-(priority-queue)eulerian-circuit

LeetCode Problem 332

Difficulty: 🔴 Hard
Topics: Array, String, Depth-First Search, Graph Theory, Sorting, Heap (Priority Queue), Eulerian Circuit

Solution

Problem Understanding

The problem is asking us to reconstruct a flight itinerary given a list of tickets. Each ticket is a one-way flight represented as a pair of airport codes [from, to]. The traveler always starts at "JFK", and the itinerary must use all tickets exactly once. If multiple valid itineraries exist, the one with the smallest lexicographical order should be returned.

The input is a list of tickets, where each airport code is a string of exactly three uppercase letters. There can be up to 300 tickets. This is a moderate-sized input, so an algorithm that is exponential in the number of tickets will not perform well.

The output is a list of strings representing the airports in the reconstructed order of travel. For example, if ["JFK", "ATL", "SFO"] is returned, it represents flights starting from JFK to ATL, and then from ATL to SFO.

Important constraints and guarantees are:

  • Every ticket can be used exactly once.
  • There is at least one valid itinerary using all tickets.
  • Airport codes are unique strings of length 3.
  • There may be multiple valid itineraries, so lexical order must be considered.

Potential edge cases include tickets with multiple destinations from the same airport, disconnected paths (although the problem guarantees connectivity), and tickets that form cycles.

Approaches

A brute-force approach would be to generate all possible permutations of tickets starting from "JFK", check which sequences use all tickets exactly once, and then select the one with the smallest lexicographical order. While this approach is correct, it is combinatorial in nature: for n tickets, there are n! possible sequences. This is clearly impractical for n = 300.

The optimal approach relies on the observation that the problem is equivalent to finding an Eulerian path in a directed graph. Each airport is a node, and each ticket is a directed edge. Since the itinerary must use all tickets exactly once, we need to traverse all edges in the graph exactly once. To ensure lexical order, we can store each airport's outgoing destinations in a priority queue or sorted list. Using Depth-First Search (DFS) with backtracking, we can recursively construct the path from "JFK" while always visiting the smallest lexical destination first. This guarantees the resulting path has the smallest lexical order.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Generate all permutations, filter valid itineraries, pick the smallest lexicographically
Optimal O(E log E) O(V + E) DFS with a priority queue for lexical order; Eulerian path ensures all edges are visited

Algorithm Walkthrough

  1. Graph Construction: Build a graph where keys are departure airports and values are min-heaps (priority queues) of destination airports. This allows us to always pick the next airport with the smallest lexical order efficiently.
  2. DFS Traversal: Start DFS from "JFK". At each airport, while there are destinations remaining in the priority queue, recursively visit the smallest lexical destination first.
  3. Post-order Path Construction: Append airports to the itinerary only after exploring all their outgoing edges. This constructs the path in reverse order because we append after visiting all deeper nodes.
  4. Reverse the Result: Since the itinerary is constructed in post-order, reverse the collected list to obtain the correct itinerary.

Why it works: The algorithm works because we are effectively performing Hierholzer's algorithm for Eulerian paths in a directed graph. Using a priority queue ensures lexical order at each decision point. Since all tickets (edges) are used exactly once, the resulting path includes every ticket, satisfying all constraints.

Python Solution

from typing import List
from collections import defaultdict
import heapq

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        for frm, to in tickets:
            heapq.heappush(graph[frm], to)
        
        result = []
        
        def dfs(airport: str):
            heap = graph[airport]
            while heap:
                next_airport = heapq.heappop(heap)
                dfs(next_airport)
            result.append(airport)
        
        dfs("JFK")
        return result[::-1]

Implementation Explanation:

We first create a graph using a dictionary of min-heaps to maintain lexical order. DFS explores each airport, always taking the smallest available destination next. We append airports after exploring all outgoing flights (post-order), ensuring all tickets are used exactly once. Finally, we reverse the result to get the itinerary in the correct order.

Go Solution

package main

import (
	"container/heap"
	"sort"
)

func findItinerary(tickets [][]string) []string {
	graph := make(map[string]*StringHeap)
	for _, t := range tickets {
		if _, ok := graph[t[0]]; !ok {
			graph[t[0]] = &StringHeap{}
		}
		heap.Push(graph[t[0]], t[1])
	}
	result := []string{}
	var dfs func(string)
	dfs = func(airport string) {
		h, exists := graph[airport]
		for exists && h.Len() > 0 {
			next := heap.Pop(h).(string)
			dfs(next)
		}
		result = append(result, airport)
	}
	dfs("JFK")
	// reverse the result
	for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
		result[i], result[j] = result[j], result[i]
	}
	return result
}

// Implement min-heap for strings
type StringHeap []string

func (h StringHeap) Len() int           { return len(h) }
func (h StringHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h StringHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *StringHeap) Push(x any) {
	*h = append(*h, x.(string))
}

func (h *StringHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

Go-specific Notes: We implement a custom min-heap for strings because the standard container/heap requires an interface. DFS logic is identical to Python, and the reversal step is done manually.

Worked Examples

Example 1:

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

Graph after heapification:

JFK -> ["MUC"]
MUC -> ["LHR"]
LHR -> ["SFO"]
SFO -> ["SJC"]

DFS Traversal:

  1. Start at JFK, pop MUC → DFS(MUC)
  2. At MUC, pop LHR → DFS(LHR)
  3. At LHR, pop SFO → DFS(SFO)
  4. At SFO, pop SJC → DFS(SJC)
  5. At SJC, no outgoing → append SJC
  6. Backtrack: append SFO, LHR, MUC, JFK

Result (reversed): ["JFK","MUC","LHR","SFO","SJC"]

Example 2:

Tickets: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

Graph after heapification:

JFK -> ["ATL", "SFO"]
ATL -> ["JFK", "SFO"]
SFO -> ["ATL"]

DFS Traversal:

  1. Start at JFK, pop ATL → DFS(ATL)
  2. At ATL, pop JFK → DFS(JFK)
  3. At JFK, pop SFO → DFS(SFO)
  4. At SFO, pop ATL → DFS(ATL)
  5. At ATL, pop SFO → DFS(SFO)
  6. At SFO, no outgoing → append SFO
  7. Backtrack: append ATL, ATL, SFO, JFK, JFK

Result (reversed): ["JFK","ATL","JFK","SFO","ATL","SFO"]

Complexity Analysis

Measure Complexity Explanation
Time O(E log E) Building heaps costs log E per edge, and DFS visits each edge once
Space O(V + E) Graph storage and recursion stack for DFS

We use a min-heap to efficiently retrieve the smallest lexical destination at each step. DFS ensures each ticket is used once.

Test Cases

# Provided examples
assert Solution().findItinerary([["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]) == ["JFK","MUC","LHR","SFO","SJC"]
assert Solution().findItinerary([["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]) == ["JFK","ATL","JFK","SFO","ATL","SFO"]

# Edge cases
assert Solution().findItinerary([["JFK","ATL"]]) == ["JFK","ATL"] # Single ticket
assert Solution().findItinerary([["JFK","ATL"],["