Reorient 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: 30-40 mins
  • 🛠️ Topics: Graph Traversal, DFS, Tree

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 connection in the connections array represent?
    • A: Each connection [airport_a, airport_b] represents a one-way flight from airport_a to airport_b.
  • Q: What is the goal of the problem?
    • A: The goal is to reorient the minimum number of flights so that every airport can send a flight to airport 0.
  • Q: How is the network of flights structured?
    • A: The network forms a tree, meaning there is exactly one path between any two airports.
HAPPY CASE
Input: 
```python
n = 6
connections = [0, 1], [1, 3], [2, 3], [4, 0], [4, 5](/codepath/compsci_guides/wiki/0,-1],-[1,-3],-[2,-3],-[4,-0],-[4,-5)
```
Output:
```markdown
3
Explanation: The initial flight routes are: 0 -> 1, 1 -> 3, 2 -> 3, 4 -> 0, 4 -> 5.
To ensure every airport can send a flight to airport 0, we need to reorient the routes [1 -> 3], [2 -> 3], and [4 -> 5].
```

EDGE CASE
Input: 
```python
n = 2
connections = [1, 0](/codepath/compsci_guides/wiki/1,-0)
```
Output:
```markdown
0
Explanation: The only flight already goes to airport 0, so no reorientation is needed.

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 Reorienting Directed Edges in a Tree, we want to consider the following approaches:

  • Graph Traversal (DFS): We can traverse the graph and count how many directed edges need to be reversed so that every airport can reach airport 0.
  • Tree Representation: Since the flight network forms a tree, we can use DFS to traverse the tree and determine which edges are incorrectly oriented.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Convert the given one-way flight routes into an undirected graph representation. Then, use DFS to explore all airports, counting the number of edges that are directed away from airport 0 and need to be reversed. Every directed edge that goes away from 0 will require reorientation.

1) Build an adjacency list for the undirected graph from the `connections`.
2) Create a set `directed_edges` to store the original one-way flight routes.
3) Define a recursive DFS function:
   a) Traverse the graph, skipping the parent node to avoid revisiting.
   b) If an edge is directed away from airport `0`, increment the `reorient_count`.
   c) Recursively visit all connected airports.
4) Start DFS from airport `0` and count the number of reorientations.
5) Return the total `reorient_count`.

⚠️ Common Mistakes

  • Forgetting to track the direction of the original edges, which can lead to incorrect reorientation counting.
  • Not handling the case where the tree is small (e.g., only one or two airports).

4: I-mplement

Implement the code to solve the algorithm.

def min_reorient_flight_routes(n, connections):
    # Create an adjacency list for the undirected graph
    graph = {i: [] for i in range(n)}
    directed_edges = set()  # Store directed edges
    
    for a, b in connections:
        graph[a].append(b)
        graph[b].append(a)
        directed_edges.add((a, b))  # Mark the original direction
    
    # DFS to count the reorientations needed
    def dfs(airport, parent):
        nonlocal reorient_count
        # Explore all neighbors
        for neighbor in graph[airport]:
            if neighbor == parent:
                continue  # Don't revisit the parent node
            # If the edge is directed away from 0 (wrong direction), increment the count
            if (airport, neighbor) in directed_edges:
                reorient_count += 1
            # Recursively visit the neighbor
            dfs(neighbor, airport)
    
    reorient_count = 0
    # Start DFS from airport 0
    dfs(0, -1)
    
    return reorient_count

5: R-eview

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

  • Input:
n = 6
connections = [0, 1], [1, 3], [2, 3], [4, 0], [4, 5](/codepath/compsci_guides/wiki/0,-1],-[1,-3],-[2,-3],-[4,-0],-[4,-5)

print(min_reorient_flight_routes(n, connections))  # Expected output: 3
  • Output:
3

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 flight routes (edges). Each airport and connection is visited once in the DFS traversal.
  • Space Complexity: O(V + E) for storing the graph and directed edges.