Problem

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:

graph LR;
A(JFK) ---> B(MUC) ---> C(LHR) ---> D(SFO) ---> E(SJC)
  
Input:
tickets =[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

Explanation: Basically we have following tickets
- MUC ➔ LHR
- JFK ➔ MUC
- SFO ➔ SJC
- LHR ➔ SFO
- MUC ➔ LHR
Finally this is our iternary: JFK ➔ MUC ➔ LHR ➔ SFO ➔ SJC

Example 2:

 %%{init: {'flowchart': { 'curve': 'linear' }}}%%
graph LR;
A(JFK) ---> C(ATL) & D(SFO)
D ---> C
C ---> D
C ---> A
  
Input:
tickets =[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output:
 ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

Solution

Some observations before we begin:

  • The graph is directed, meaning a ticket from city A to B does not imply a ticket from city B to A.
  • The tickets are guaranteed to form valid routes.
  • To find the lexicographically smallest route when multiple paths exist, we must either sort the tickets list or use a PriorityQueue. A greedy approach won’t work due to potential cycles in the graph.

Method 1 - Brute Force

Let’s revisit the brute force approach for this problem, which involves checking every possible permutation of flights to ensure a valid itinerary. This method has a time complexity of O(n!). Now, consider whether we can enhance this solution using backtracking.

Method 2 - Topological Sorting

One approach is to construct a graph and perform Topological Sorting on it. This solution has a time complexity of O(n).

Method 3 - Hierholzer Algorithm (DFS)

This utilizes Hierholzer’s algorithm to identify a Euler Path, similar to the Euler Graphs - Origin of Graph Theory - Seven bridges of Konigsberg.

Given that a Eulerian path exists, the graph must be Eulerian.

Starting from “JFK,” we can apply Hierholzer’s algorithm to find a Eulerian path, ensuring a valid reconstruction.

A PriorityQueue is preferable to a TreeSet due to duplicate entries.

Since the problem requires the lexicographically smallest solution, a min-heap for neighbours ensures we always visit the smallest possible neighbour first.

Hashing can be used to bypass constructing a graph. The starting point will never appear on the ‘to’ side of a ticket. Once identified, traverse the map to return the itinerary in order.

Algorithm

First, proceed forward until you can go no further, forming a main path. Remaining tickets form cycles, which merge into the main path on the way back. By writing the path backwards when retreating, merging cycles is straightforward—the end part is already written, and the start part has yet to be written, so write the cycle then and continue writing the path backwards.

Example

Starting from JFK, we first travel JFK -> A -> B -> D -> A. Upon reaching a dead end, we record A as the end of the route and backtrack to D. Spotting an unused ticket, we follow D -> C -> B -> JFK -> D. Hitting another dead end, we write down each airport on the way back: D before the previously written A, then JFK before D, and so on. After completing the cycle at D, the current route is D -> C -> B -> JFK -> D -> A. Continuing to backtrack, we prepend B, A, and finally JFK to the sequence, resulting in JFK -> A -> B -> D -> C -> B -> JFK -> D -> A.

Code

Java
Recursive DFS

Map<String, PriorityQueue<String>> map = new HashMap<>();
List<String> ans = new LinkedList<>();
	
public List<String> findItinerary (List<List<String>> tickets) {
	for (List<String> ticket: tickets) {
		map.putIfAbsent(ticket.get(0), new PriorityQueue<String>())
		map.get(ticket.get(0)).offer(ticket[1]);
	}

	
	dfs("JFK");
	return result;
}

public void dfs(String s) {
	PriorityQueue<String> q = map.get(s);

	while (q != null && !q.isEmpty()) {
		dfs(q.poll());
	}

	result.addFirst(s);
}
Iterative DFS
public List<String> findItinerary(List<List<String>> tickets) {
		Map<String, PriorityQueue<String>> graph = new HashMap<>();
		for (List<String> ticket : tickets) {
			graph.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>()).add(ticket.get(1));
		}
		Stack<String> stack = new Stack<>();
		LinkedList<String> ans = new LinkedList<>(); // using LinkedList instead of List as we have addFirst(value) function faster than add(0, value)
		stack.push("JFK");
		while (!stack.isEmpty()) {
			String src = stack.peek();
			// key may not be in graph in case it is like final destination, for eg. see SJC in test case
			if (!graph.containsKey(src) || graph.get(src).isEmpty()) { //No further travel possible
				ans.addFirst(src); // adding at start otherwise we have to rverse
				stack.pop();
			} else {
				String dst = graph.get(src).poll();
				stack.push(dst);
			}
		}
		return ans;
}