# Backtracking - Reconstruct Itinerary

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

DFS, Backtracking

## 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.

**Example 1:**

1
2

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

**Example 2:**

1
2
3

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

The generic solution expected here is not a Hard one however the generic `dfs()`

solution with backtracking will get TimeOut Error in LeetCode. Unless you memorize, it won’t be easy to find the best solution which will pass LeetCode in 15-20mins.

The question completes the language by mentioning **lexical ordering**, which is actually the easier part to implement. Let’s start without this requirement and add it once we have basic solution in place.

Like other graph problem, we need the adjacency list.

1
2
3

adjacency_list= collections.defaultdict(list)
for src,dest in tickets:
adjacency_list[src].append(dest)

We need an `output`

array to store the itinerary.

1

output = []

Now start the `dfs()`

, it takes the `src`

as the input and traverse through all possible neighbors based on the `adjacency_list`

. When the length of `output`

matches with the `tickets`

we know that we were able to traverse through all the `tickets`

.

We have to add `+1`

as we are stating from `JFK`

and we are going to always have one less ticket than the number of destinations.

1
2
3

def dfs(src):
if len(output)==len(tickets)+1:
return True

In case at some point we find that a node is not traversable, we can return `False`

1
2

if src not in adjacency_list:
return False

We will use **template 2** that we have already discussed here.

This is kinda straight forward, we need to get all the neighbors of the current node. Then `pop()`

is out from the `adjacency_list`

so that we don’t travel in cycles. Then add it to the `output`

and recursively call `dfs()`

by providing the `dest`

.

If anytime the `dfs()`

returns `True`

, we return `True`

. Otherwise the path was not successful and we backtrack from the current `dest`

and add it back to the `adjacency_list`

.

1
2
3
4
5
6
7
8
9

for index, dest in enumerate(adjacency_list):
adjacency_list[src].pop(index)
outout.append(dest)
if dsf(dest):
return True
adjacency_list[src].insert(index, dest)
outout.pop()

Finally, call `dfs()`

by passing `JSK`

as the first node and return `outout`

.

1
2

dfs('JFK')
return output

If you have understood so far, then incorporating the **lexical ordering** is very straightforward. During an interview, you can just sort the neighbors before traversing. This would be the most natural way of solving this.

1
2
3
4

neighbors=adj[src]
neighbors.sort()
for i, dst in enumerate(neighbors):
...

You can also then think about pre-sorting the `tickets`

array so that the sorting is done only once.

1
2
3
4
5

tickets.sort()
adjacency_list= collections.defaultdict(list)
for src,dest in tickets:
...

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def find_itinerary(tickets):
tickets.sort()
adjacency_list= collections.defaultdict(list)
for src,dest in tickets:
adjacency_list[src].append(dest)
output = []
def dfs(src):
if len(output)==len(tickets) + 1:
return True
if src not in adjacency_list:
return False
for index, dest in enumerate(adjacency_list):
adjacency_list[src].pop(index)
outout.append(dest)
if dsf(dest):
return True
adjacency_list[src].insert(index, dest)
outout.pop()
dfs('JFK')
return output