Description
You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.
All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.
- For example, the itinerary
["JFK", "LGA"]has a smaller lexical order than["JFK", "LGB"].
You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
Examples:
Example 1:
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]
Example 2:
Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]Solution in Python
Approach:
- Graph Representation:
- Use a dictionary where the keys are the departure airports and the values are lists of arrival airports.
- The lists of arrival airports should be maintained in lexicographical order for each departure airport to ensure that we pick the smallest airport first.
- Eulerian Path:
- The task is to find an Eulerian path (a path that visits every edge exactly once) since we must use all tickets exactly once. This can be efficiently done using a hierarchical depth-first search (DFS) or by leveraging the stack-based Eulerian path construction (iterative DFS).
- Start the DFS from “JFK”. When visiting a node (airport), recursively visit its neighbors (next destination). Once you exhaust all the neighbors, backtrack and add the airport to the result.
- Hierarchical DFS:
- We visit airports in lexicographical order by sorting the destinations. Each time we visit an airport, we remove that edge from the graph.
- Once all flights are used up, the backtrack will ensure that the itinerary is constructed in reverse order, so we reverse it before returning.
Python
from collections import defaultdict
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
# Build the adjacency list (graph)
graph = defaultdict(list)
# Sort tickets in reverse lexicographical order and build the graph
# We reverse sort because we'll be popping destinations from the end of the list
for from_airport, to_airport in sorted(tickets, reverse=True):
graph[from_airport].append(to_airport)
# Initialize result itinerary
itinerary = []
# Define the DFS function
def dfs(airport):
# While there are destinations left from this airport
while graph[airport]:
# Visit the next destination (smallest due to reverse sorting)
next_airport = graph[airport].pop()
dfs(next_airport)
# Once all connections from this airport are visited, add to itinerary
itinerary.append(airport)
# Start the DFS from 'JFK'
dfs("JFK")
# The itinerary is built in reverse, so reverse it at the end
return itinerary[::-1]Explanation:
- Graph Construction:
- We use a
defaultdict(list)to represent the adjacency list of the graph. For each ticket, we store the destination airport as a neighbor of the departure airport. - We sort the tickets in reverse lexicographical order because we will be popping elements from the end of the list, and we want to ensure that the smallest destination comes first.
- We use a
- Depth-First Search (DFS):
- The
dfs()function recursively visits each airport. For each airport, we pop the next destination (smallest lexicographical one) and recursively visit it. - Once all destinations from the current airport are visited, we append that airport to the
itinerary.
- The
- Itinerary Construction:
- Since we are using DFS, the order of visited airports is reversed. The correct itinerary is obtained by reversing the result at the end.
Time Complexity:
- O(E log E), where E is the number of edges (tickets). Sorting the tickets takes O(E log E), and the DFS visit for each ticket takes O(E). The overall complexity is dominated by the sorting step.
Space Complexity:
- O(V + E), where V is the number of vertices (airports) and E is the number of edges (tickets). We store the graph in memory, which uses O(V+E) space. Additionally, the recursive DFS call stack may use up to O(V) space.
Solution in C++
C++
class Solution {
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
// Adjacency list where destinations are stored in sorted order
unordered_map<string, multiset<string>> adj;
// Populate the adjacency list (graph)
for (auto& ticket : tickets) {
adj[ticket[0]].insert(ticket[1]);
}
vector<string> itinerary;
stack<string> dfsStack;
dfsStack.push("JFK");
while (!dfsStack.empty()) {
string airport = dfsStack.top();
// If there are no more destinations to explore from the current airport
if (adj[airport].empty()) {
itinerary.push_back(airport);
dfsStack.pop();
} else {
// Visit the smallest lexicographical destination
auto next_airport = adj[airport].begin();
dfsStack.push(*next_airport);
adj[airport].erase(next_airport); // Remove the ticket (edge)
}
}
// The itinerary is constructed in reverse order, so reverse it before returning
reverse(itinerary.begin(), itinerary.end());
return itinerary;
}
};Solution in Javascript
JavaScript
var findItinerary = function(tickets) {
// Step 1: Create a graph where each airport (key) has a list of destination airports (values).
// Sort destinations in lexical order so that we can always pick the smallest lexical destination first.
let graph = {};
tickets.forEach(([from, to]) => {
if (!graph[from]) {
graph[from] = [];
}
graph[from].push(to);
});
// Sort the adjacency list (destination airports) in lexical order for each airport.
for (let airport in graph) {
graph[airport].sort();
}
// Step 2: Initialize the result itinerary array and a stack for depth-first search (DFS).
let itinerary = [];
let stack = ['JFK']; // The itinerary must begin with "JFK" as per the problem.
// Step 3: Perform DFS to build the itinerary.
while (stack.length > 0) {
let currentAirport = stack[stack.length - 1]; // Peek at the top of the stack
// If the current airport has a destination to visit, we visit the next lexically smallest one.
if (graph[currentAirport] && graph[currentAirport].length > 0) {
stack.push(graph[currentAirport].shift()); // Pop the smallest destination from the adjacency list
} else {
// If there are no more destinations to visit from this airport, add it to the itinerary.
itinerary.push(stack.pop());
}
}
// The itinerary is constructed in reverse order, so we need to reverse it before returning.
return itinerary.reverse();
};Solution in Java
Java
import java.util.*;
class Solution {
// This method reconstructs the itinerary from the tickets
public List<String> findItinerary(List<List<String>> tickets) {
// Graph to store the adjacency list where each departure airport maps to a priority queue of destination airports
Map<String, PriorityQueue<String>> graph = new HashMap<>();
// Build the graph (adjacency list) using the tickets
for (List<String> ticket : tickets) {
String from = ticket.get(0); // departure airport
String to = ticket.get(1); // destination airport
// If the departure airport is not yet in the graph, add it
graph.putIfAbsent(from, new PriorityQueue<>());
// Add the destination airport to the priority queue of the departure airport
graph.get(from).offer(to);
}
// List to store the final itinerary
List<String> itinerary = new LinkedList<>();
// Start DFS from 'JFK'
dfs("JFK", graph, itinerary);
// Since we added airports in reverse order during DFS, reverse the result list
Collections.reverse(itinerary);
return itinerary;
}
// Depth-first search function to traverse the graph
private void dfs(String airport, Map<String, PriorityQueue<String>> graph, List<String> itinerary) {
// While there are still destinations to visit from the current airport
while (graph.containsKey(airport) && !graph.get(airport).isEmpty()) {
// Get the lexicographically smallest destination airport
String nextAirport = graph.get(airport).poll();
// Recur on the next airport
dfs(nextAirport, graph, itinerary);
}
// Post-order addition of the airport to the itinerary
itinerary.add(airport);
}
}