Find Itinerary II - codepath/compsci_guides GitHub Wiki

Unit 10 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Graphs, Depth First Search (DFS), Topological Sort, Pathfinding

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What does each element in boarding_passes represent?
    • A: Each element (departure, arrival) represents a flight from departure to arrival.
  • Q: How do we find the itinerary?
    • A: We need to construct the graph, perform DFS, and add each airport to the itinerary after visiting all its destinations.
  • Q: What if there are multiple valid itineraries?
    • A: Sorting the destinations in lexicographical order ensures that the itinerary follows the correct order if required.
HAPPY CASE
Input: boarding_passes = [
                    (""JFK"", ""ATL""),
                    (""SFO"", ""JFK""),
                    (""ATL"", ""ORD""),
                    (""LAX"", ""SFO"")]
Output: ['LAX', 'SFO', 'JFK', 'ATL', 'ORD']
Explanation: The correct itinerary starts at LAX and proceeds through all destinations.

EDGE CASE
Input: boarding_passes = [
                    (""LAX"", ""DXB""),
                    (""DFW"", ""JFK""),
                    (""LHR"", ""DFW""),
                    (""JFK"", ""LAX"")]
Output: ['LHR', 'DFW', 'JFK', 'LAX', 'DXB']
Explanation: The itinerary proceeds through the correct order starting from LHR.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Graph Traversal problems, we want to consider the following approaches:

  • DFS (Depth First Search): This is suitable for traversing the graph and ensuring that we visit all airports and construct the correct itinerary in reverse order.
  • Adjacency List Construction: We will represent the flights as a directed graph using an adjacency list.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use DFS to visit all the destinations for each airport and construct the itinerary in reverse order. The key challenge is ensuring that we visit airports in the correct order, which is achieved by sorting the destination list.

1) Create an adjacency list `flights` to represent the directed graph. The key is the departure airport, and the value is a list of destination airports.
2) Sort the destination airports for each departure in reverse lexicographical order (so we can pop elements in correct order).
3) Define a recursive DFS function `dfs(airport)` that visits all destinations of `airport`.
   a) Pop each destination from the adjacency list and recursively call `dfs` for that destination.
   b) Once all destinations are visited, append the current airport to the result list.
4) Start DFS from the starting airport (first departure).
5) Reverse the result list to obtain the correct itinerary.

⚠️ Common Mistakes

  • Forgetting to reverse the result list after DFS traversal, which will produce the wrong order.
  • Failing to sort destinations lexicographically, which may result in incorrect output when there are multiple possible itineraries.

4: I-mplement

Implement the code to solve the algorithm.

from collections import defaultdict

def find_itinerary(boarding_passes):
    # Step 1: Build the graph (adjacency list)
    flights = defaultdict(list)
    
    # Create adjacency list where each airport has a list of destinations
    for departure, arrival in boarding_passes:
        flights[departure].append(arrival)
    
    # Step 2: Sort the destinations for each departure airport (optional)
    # This ensures we visit in lexicographical order if required
    for airport in flights:
        flights[airport].sort(reverse=True)

    # Step 3: Perform DFS and build the itinerary
    result = []
    
    def dfs(airport):
        # Visit all the destinations for the current airport
        while flights[airport]:
            next_flight = flights[airport].pop()
            dfs(next_flight)
        # Once all destinations are visited, add the airport to the result
        result.append(airport)

    # Step 4: Start DFS from the starting airport
    start_airport = boarding_passes[0][0]  # Assumption: we start from the first departure
    dfs(start_airport)
    
    # Step 5: The itinerary will be in reverse order due to DFS, so reverse the result
    return result[::-1]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input:
boarding_passes_1 = [
                    (""JFK"", ""ATL""),
                    (""SFO"", ""JFK""),
                    (""ATL"", ""ORD""),
                    (""LAX"", ""SFO"")]

boarding_passes_2 = [
                    (""LAX"", ""DXB""),
                    (""DFW"", ""JFK""),
                    (""LHR"", ""DFW""),
                    (""JFK"", ""LAX"")]

print(find_itinerary(boarding_passes_1))  # Output: ['LAX', 'SFO', 'JFK', 'ATL', 'ORD']
print(find_itinerary(boarding_passes_2))  # Output: ['LHR', 'DFW', 'JFK', 'LAX', 'DXB']

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(E log E), where E is the number of edges (flights). Sorting the destinations takes O(E log E), and DFS visits each edge exactly once.
  • Space Complexity: O(E + V), where E is the number of edges and V is the number of vertices (airports), for storing the adjacency list and result list.