Find All Flight Routes - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-35 mins
  • 🛠️ Topics: Graph Traversal, DFS, DAG

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 the flight_routes list represent?
    • A: Each index i in flight_routes represents an airport, and the corresponding list contains the airports that can be reached directly from airport i.
  • Q: What is the goal of the problem?
    • A: The goal is to find all possible paths from airport 0 to the last airport (labeled n - 1).
  • Q: How should the paths be returned?
    • A: The function should return all possible flight paths in any order.
HAPPY CASE
Input: 
```python
flight_routes_1 = [1, 2], [3], [3], [](/codepath/compsci_guides/wiki/1,-2],-[3],-[3],-[)

Output:

[0, 1, 3], [0, 2, 3](/codepath/compsci_guides/wiki/0,-1,-3],-[0,-2,-3)
Explanation: 
There are two possible flight paths from airport 0 to airport 3: 
- Path 1: 0 -> 1 -> 3 
- Path 2: 0 -> 2 -> 3

EDGE CASE Input:

flight_routes_2 = [4,3,1],[3,2,4],[3],[4],[](/codepath/compsci_guides/wiki/4,3,1],[3,2,4],[3],[4],[)

Output:

[0, 4], [0, 3, 4], [0, 1, 3, 4], [0, 1, 2, 3, 4], [0, 1, 4](/codepath/compsci_guides/wiki/0,-4],-[0,-3,-4],-[0,-1,-3,-4],-[0,-1,-2,-3,-4],-[0,-1,-4)
Explanation: 
There are five possible flight paths from airport 0 to airport 4.

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 All Path Finding in a DAG, we want to consider the following approaches:

  • Depth First Search (DFS) with backtracking: DFS allows us to explore all possible paths from airport 0 to airport n - 1, while backtracking helps explore all potential routes by undoing partial paths.
  • Directed Acyclic Graph (DAG): Since the graph is a DAG, we are guaranteed that there are no cycles, making it safe to use DFS to explore all possible paths.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS to explore all possible paths from the starting airport 0 to the destination airport n - 1. During DFS, track the current path, and whenever we reach the destination, add the path to the result. Backtrack after exploring each path to allow other routes to be explored.

1) Initialize an empty `result` list to store all valid paths.
2) Define a recursive DFS function:
   a) Add the current airport to the current path.
   b) If the current airport is the final destination (i.e., `n - 1`), add the current path to the result list.
   c) Otherwise, recursively explore all neighboring airports from the current airport.
   d) Backtrack by removing the current airport from the path after exploring all routes.
3) Start DFS from airport `0` and explore all paths.
4) Return the `result` list.

⚠️ Common Mistakes

  • Forgetting to backtrack, which could result in incomplete paths or infinite recursion.
  • Not correctly handling cases where there are no outgoing flights from an airport, which should naturally end the current path.

4: I-mplement

Implement the code to solve the algorithm.

def find_all_flight_routes(flight_routes):
    result = []
    path = []
    
    def dfs(airport):
        path.append(airport)
        
        # If we reached the final airport, add the path to the result
        if airport == len(flight_routes) - 1:
            result.append(path.copy())
        else:
            # Explore all possible next airports
            for next_airport in flight_routes[airport]:
                dfs(next_airport)
        
        # Backtrack to explore other routes
        path.pop()
    
    # Start DFS from airport 0
    dfs(0)
    
    return result

5: R-eview

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

  • Input:
flight_routes_1 = [1, 2], [3], [3], [](/codepath/compsci_guides/wiki/1,-2],-[3],-[3],-[)
flight_routes_2 = [4,3,1],[3,2,4],[3],[4],[](/codepath/compsci_guides/wiki/4,3,1],[3,2,4],[3],[4],[)

print(find_all_flight_routes(flight_routes_1))  # Expected output: [0, 1, 3], [0, 2, 3](/codepath/compsci_guides/wiki/0,-1,-3],-[0,-2,-3)
print(find_all_flight_routes(flight_routes_2))  # Expected output: [0, 4], [0, 3, 4], [0, 1, 3, 4], [0, 1, 2, 3, 4], [0, 1, 4](/codepath/compsci_guides/wiki/0,-4],-[0,-3,-4],-[0,-1,-3,-4],-[0,-1,-2,-3,-4],-[0,-1,-4)
  • Output:
[0, 1, 3], [0, 2, 3](/codepath/compsci_guides/wiki/0,-1,-3],-[0,-2,-3)
[0, 4], [0, 3, 4], [0, 1, 3, 4], [0, 1, 2, 3, 4], [0, 1, 4](/codepath/compsci_guides/wiki/0,-4],-[0,-3,-4],-[0,-1,-3,-4],-[0,-1,-2,-3,-4],-[0,-1,-4)

6: E-valuate

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

  • Time Complexity: O(V + E), where V is the number of airports (vertices) and E is the number of flights (edges). Each airport and its connections are visited once in the DFS traversal.
  • Space Complexity: O(V) for storing the current path and the recursion stack.