Solution Developed In:

The Question

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.

Question:

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.

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

Explaining The Question

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.

Recommended Knowledge

1. Graph Theory
2. Adjacency List
3. Depth First Search
4. Backtracking
5. Topological Sort
6. Lexicographical Order
7. Directed Graph

What do we know?

1. 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.
2. We know we need to visit in lexicographical order first.

How we're going to do it:

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.

1. Firstly, we're going to Topological Sort our tickets array. This will give us a lexicographically sorted array of cities.
2. With this array, we're going to create an Adjacency List where each city has it's airport arrivals are lexicographically sorted.
3. 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.
4. We're adding the airports in Topological Order to a stack. This stack is going to be our return value for this entire problem.
5. 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.

Big O Notation:

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

Could this be improved? Yes, with Eulerian Path.I choose the DFS because it's the intuitive way to go. While Eulerian Path is faster, it isn't something you could just come up with.

Leetcode Results:

See Submission Link:

• Runtime: 113 ms, faster than 71.71% of JavaScript online submissions for Max Area of Island
• Memory Usage: 50 MB, less than 21.34% of JavaScript online submissions for Max Area of Island.

The Solution

/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function (tickets) {

    // We have been given a directed graph.
    // We know we always start at JFK.
    // We need to return the flight path the user took.
    // We will use a adjacency list to store the graph.
    // Node -> [destination, destination, destination]

    // For each node we visit in topological order, we add to the path.
    // Starting with JFK and the lexicographically closest node.
    // Although the issue is that it isn't going to always be right.
    // We could accidentally take a node that is lexicographically correct
    // but is just the last destination in a series of travels. Meaning
    // the man has traveled the entire world, came back to Jfk and gone to the last
    // dest. Which we cannot miss, so we check this. If a node has no given edges,
    // and it isn't the last destination, we backtrack our results. Act as if we haven't
    // visited him yet and do the rest, repeating this logic.

    // We repeat this until we have visited all nodes, we know this by the size of our
    // output array matching the size of our input array or we just have no more nodes with edges
    // anymore.

    // Flights paths will be our adjacency list.
    const flight_paths = new Map();

    // This is what we will return, we always know we start at JFK.
    const flight_path_order = ["JFK"];

    // Thankfully, javascript's default sort is lexicographical.
    // We do this as we need to visit the lexicographically closest node first.
    // Assuming we don't backtrack on it later.
    tickets = tickets.sort(); // O(n^2);

    // Create the adjacency list.
    for (const [source, dest] of tickets) {
        let edges = [];
        if (flight_paths.has(source)) {
            edges = flight_paths.get(source);
        }
        edges.push(dest);
        flight_paths.set(source, edges);
    }

    // Depth first search.
    const depth_first_search = (city) => {
        // Have we already been to all the nodes?
        // Meaning we have visited all the tickets?
        if (flight_path_order.length === tickets.length + 1) return true;

        // Get the departures of flights from this city.
        // If their isn't any, we need to back track on this node
        // Because we know we have more flights to go and we have already
        // somehow visited our destination. Which is incorrect.
        const cities_to_go_to = flight_paths.get(city) || [];
        if (!cities_to_go_to.length) return false;

        // So we have other cities to go to from here.
        // Let's create a copy of those cities because we're going to
        // be dynamically adding and removing from that array. Something our
        // for loop wouldn't be able able to handle otherwise.
        const cities_copied = Array.from(cities_to_go_to);

        // Visit all connecting cities.
        for (const other_city of cities_copied) {
            // Add to our output, as we're doing this in topological sort
            flight_path_order.push(other_city);

            // Remove the city from the edges of the graph.
            // As we don't want to revisit it. Otherwise we would have a loop.
            // Note: we're passing this array by reference. So we don't need to re-set it.
            // We use shift here because we've done this in lexicographical order starting from
            // the beginning.
            cities_to_go_to.shift();

            // If it returns true, it mean's we've visited all cities
            // and that mean's we have nothing else to do.
            if (depth_first_search(other_city)) {
                return flight_path_order;
            } else {
                // BACKTRACKING!
                // We've visited the wrong city!
                // Undo our work here, as this is not the right city,
                // we need to revisit this city later on and not now.
                // What this does is visit all other cities
                // then backtrack on this city.
                flight_path_order.pop();
                cities_to_go_to.push(other_city);
            }
        }

        return false;
    };

    // Start at JFK airport
    return depth_first_search("JFK");

    // In the end this is O (v + e) ^ 2 time O(e) space
    // We could better solve this using Eulerian path.
};