For this article we will be covering Leetcode's '332. Reconstruct Itinerary' question. This question is the first
Boss Battle of the Graph Questions. You will find that to solve this question, you will need to know lot's of Graph Patterns. This is no simple question.
You are given a list of airline
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.
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"]
This Question is rated Hard. Which is very accurate. This question combines a handful of Graph Patterns, making it very difficult to solve. Despite this, this is an excellent question to learn all of those concepts.
We're given an array of tickets, where each ticket contains a departure and arrival airport. We need to reconstruct the itinerary in order and return it. We always know we start at JFK.
We need to perform Depth First Search on a Adjacency List where each city has it's airport arrivals lexicographically sorted. Where we need to return the Topological Sort from JFK to the last destination. As this is a Directed Graph, we need to also implement backtracking just in case we accidentally go to the last destination too early.
Lot's of concepts to know. It's a very interesting question.
- Graph Theory
- Adjacency List
- Depth First Search
- Topological Sort
- Lexicographical Order
- Directed Graph
- We're given a list of tickets, where each ticket contains a departure and arrival airport. We need to reconstruct the itinerary in order and return it.
- We know we need to visit in lexicographical order first.
Well, we know we can build an Adjacency List where each city has it's airport arrivals are lexicographically sorted. Lexicographical order is the order in which the letters are sorted in a word (A fancy way of saying alphabetical order 😁). Given this information, we know each departure at each airport, but we just don't know the full order, it may be lexicographically sorted but that may not be the order the ticket owner traveled by. The ticket owner didn't travel in lexicographic order.
So given this information, we can perform Depth First Search on this graph. To explore each airport from it's source. While we're travelling in our Depth First Search, we're removing that airport from the current node, because we do want to revisit this airport, just not again from this airport. So we remove it from the adjacency list edges.
During this Depth First Search, we're adding the cities we visit in Topological Order to a stack. This stack will be our itinerary. We're always checking if we're going in the correct direction, we know this by checking the length of the tickets array and if we're at the last ticket, and we have children still to visit, then we're going the wrong way. So in this situation, we're going to use Backtracking to go back to the last city we visited and try another route until we fully construct our itinerary.
- Firstly, we're going to Topological Sort our tickets array. This will give us a lexicographically sorted array of cities.
- With this array, we're going to create an Adjacency List where each city has it's airport arrivals are lexicographically sorted.
- We will then perform Depth First Search on this graph, for each city, we remove it's edges from the adjacency list, as to not revisit that city again from this airport.
- We're adding the airports in Topological Order to a stack. This stack is going to be our return value for this entire problem.
- We need to check if we're going in the correct direction, we do this by checking the length of the tickets array, if we have no children, then we're going the wrong way. So we're going to use Backtracking to go back to the last city we visited and try another route until we fully construct our itinerary. We remove it from our stack, and we're going to try another route.
- Time Complexity: O( (V * E) ^ 2 ) / O(n ^ 2) | Where V is the number of vertices and E is the number of edges. It's (V * E) because we're going to perform Depth First Search and visit every node. And it's (V * E) ^ 2 because we're going to perform Depth First Search on each node, and potentially visit each node again due to the Backtracking situation. As we don't know the order, in the worst case we might have to visit each node multiple times.
- Space Complexity: O(h) | Where h is the size of the call stack. Because we perform Depth First Search on each node, and we're going to add each node to the call stack.
The Big O Notation analysis for this problem is a little confusing as it combines a handful of different concepts all with their own Big O Notations. I could be wrong, let me know.
See Submission Link: