332. Reconstruct Itinerary

Hard

Problem:

Using a list of airline tickets composed of [from, to], construct an itinerary starting from JFK. If multiple itineraries exist, visit them in lexical order.

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.

https://leetcode.com/problems/reconstruct-itinerary/

Solution:

Failed Code

Test data: ["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]

Here are the issues with the code:

1. Using a list for visit: Using a list to check if a ticket is visited is inefficient. It's better to use a dictionary to keep track of the frequency of each ticket and decrement the count as you use them.

2. Sorting by the second element: Sorting only by the second element of the ticket is not sufficient. You should sort by both the departure and arrival airports to ensure the smallest lexical order.

3. Not backtracking: In dfs function, after exploring a path, it should backtrack by marking the ticket as unvisited. This is essential to explore all possible paths.

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        result = []
        visit = []

        # Smaller lexical order
        def take_second(elem):
            return elem[1]
        sorted_tickets = sorted(tickets, key=take_second)

        def dfs(index, path):
            if index == len(sorted_tickets):
                result.append(path)
                return
            for ticket in sorted_tickets:
                if ticket[0] == path[-1] and ticket not in visit:
                    visit.append(ticket)
                    dfs(index + 1, path + [ticket[1]])

        dfs(0, ["JFK"])
        return result[0] if len(result) > 0 else result

Modified Code (Stack)

The solution below uses a depth-first search to traverse the graph. The dfs function visits each airport and exhausts all its destinations before appending the airport to the result. Since we want the itinerary to start from JFK, we reverse the result to get the correct order.

from collections import defaultdict

class Solution:
    def findItinerary(tickets: List[List[str]]) -> List[str]:
        # Create a graph with the tickets
        graph = defaultdict(list)
        
        # Sort in reverse so we can use pop() for smallest lexical order
        for src, dest in sorted(tickets, reverse=True):  
            graph[src].append(dest)
    
        result = []
    
        def dfs(airport):
            while graph[airport]:
                dfs(graph[airport].pop())
            result.append(airport)
    
        dfs("JFK")
        return result[::-1]  # Reverse the result to get the correct order

for src, dest in sorted(tickets, reverse=True):

The reason for this behavior is due to the way you're constructing the graph. When you sort the tickets using:

pythonCopy codefor src, dest in sorted(tickets, reverse=True):

You're sorting the tickets in reverse order based on their lexical order. This means that the ticket ["JFK", "NRT"] will come before ["JFK", "KUL"] in the sorted list.

>>> sorted(tickets, reverse=True)
[['NRT', 'JFK'], ['JFK', 'NRT'], ['JFK', 'KUL']]

When you then construct the graph, you're appending destinations to the source airport's list. Since ["JFK", "NRT"] is processed before ["JFK", "KUL"], "NRT" is appended to JFK's list before "KUL".

This reverse sorting is intentional. By sorting in reverse and then using the pop() method (which removes the last element of a list) during the DFS traversal, you're effectively getting the smallest lexical order without having to manage the list's indices. This is a neat trick to simplify the code and make it more efficient.

➡️ More about defaultdict: defaultdict(argument)

➡️ More about sorted: sorted()

---

DFS (Queue)

1. Construct the graph in lexical order.

2. Use pop() to make recursive calls and add all the elements to the result. The results will be stored in reverse order in the list, and since we've used pop(), that path will disappear from the graph, preventing revisits.

3. Since we created the graph in lexical order, we need to read the first value using pop(0). In other words, we need to perform queue operations.

4. Finally, reverse the list so that the first value read in lexical order becomes the first value again.

import collections

class Solution:
    def findItinerary(tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        
        for a, b in sorted(tickets): # [a, b]
            graph[a].append(b)
        
        route = []
        def dfs(a):
            while graph[a]:
                popped = graph[a].pop(0)
                dfs(popped)
            route.append(a)
        
        dfs("JFK")
        return route[::-1]

Popping the last value using pop() is $O(1)$, but popping the first value with pop(0) is $O(n)$. Therefore, for a more efficient implementation, improvements are needed to process using pop(), that is, using stack operations.

Hence, if we construct the graph in reverse order from the start, extraction can be processed using pop().

Iteration

1. To avoid revisiting a location that has been previously visited, you can either mark it to avoid visiting it again, or you can remove the value using the stack's pop() method. In this case, since we're using a stack, we'll remove the value entirely using pop().

2. If there are values in the graph, extract the first value using pop(0) and insert it into the stack variable, stack (queue operation).

3. If there is a possibility of the path being disconnected, not all paths can be stored in the stack at once. Therefore, another variable is needed to unpack the values from the stack in reverse by using pop().

4. Finally, reverse the list so that the first value read in lexical order becomes the first value again.

import collections

class Solution:
    def findItinerary(tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        
            
    for a, b in sorted(tickets):
        graph[a].append(b)
    
    route, stack = [], ['JFK']
    while stack:
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop(0))
        route.append(stack.pop())
            
    return route[::-1]