Number of Airline Regions - codepath/compsci_guides GitHub Wiki

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

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

Problem Highlights

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

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 value in the matrix is_connected[i][j] = 1 represent?
    • A: It means that there is a direct flight between airport i and airport j.
  • Q: How do we define a ""region""?
    • A: A region is a group of airports that are directly or indirectly connected to each other, and no airport outside the group is connected to any airport inside the group.
  • Q: What traversal method should we use to explore connected airports?
    • A: Depth First Search (DFS) is suitable for exploring all airports in a connected component (region).
HAPPY CASE
Input: is_connected = [
                      [1, 1, 0],  # Airport 0
                      [1, 1, 0],  # Airport 1
                      [0, 0, 1]   # Airport 2
                     ]
Output: 2
Explanation: Airports 0 and 1 are directly connected, forming one region, while airport 2 is isolated, forming another region.

EDGE CASE
Input: is_connected = [
                      [1, 0, 0, 1],  # Airport 0
                      [0, 1, 1, 0],  # Airport 1
                      [0, 1, 1, 0],  # Airport 2
                      [1, 0, 0, 1]   # Airport 3
                     ]
Output: 2
Explanation: Airports 0 and 3 are connected, forming one region, and airports 1 and 2 are connected, forming another region.

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 Connected Components problems, we want to consider the following approaches:

  • DFS (Depth First Search): DFS is ideal for exploring all airports in a connected component (region) and marking them as visited.
  • Union Find (Alternative Approach): We could also use the Union-Find data structure to group airports into connected components.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use DFS to explore each connected component (region) of airports. For each unvisited airport, we initiate a DFS to visit all connected airports and mark them as visited. Every time we start a new DFS from an unvisited airport, we increment the count of regions.

1) Initialize a `visited` set to keep track of visited airports.
2) Define a recursive DFS function `dfs(i)` that explores all airports connected to airport `i`.
   a) Mark airport `i` as visited.
   b) For each airport `j`, if there is a direct flight between `i` and `j` and `j` has not been visited, recursively call `dfs(j)`.
3) Iterate through all airports. If an airport `i` has not been visited, initiate a DFS from `i` and increment the region count.
4) Return the total number of regions.

⚠️ Common Mistakes

  • Forgetting to mark airports as visited, leading to infinite loops or incorrect region counting.
  • Not handling isolated airports correctly (airports with no connections).

4: I-mplement

Implement the code to solve the algorithm.

def num_airline_regions(is_connected):
    n = len(is_connected)  # Number of airports
    visited = set()  # Set to track visited airports
    num_regions = 0  # Count of connected components (regions)

    def dfs(i):
        # Perform DFS to visit all airports in this region
        visited.add(i)
        for j in range(n):
            if is_connected[i][j] == 1 and j not in visited:
                dfs(j)

    # Iterate through all airports
    for i in range(n):
        if i not in visited:
            # New region found, do DFS from this airport
            dfs(i)
            num_regions += 1
    
    return num_regions

5: R-eview

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

  • Input:
is_connected1 = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1]
]

is_connected2 = [
    [1, 0, 0, 1],
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [1, 0, 0, 1]
]

print(num_airline_regions(is_connected1))  # Output: 2
print(num_airline_regions(is_connected2))  # Output: 2

6: E-valuate

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

  • Time Complexity: O(n^2), where n is the number of airports. DFS explores each node and checks all connections for each airport.
  • Space Complexity: O(n) for storing the visited set and the recursion stack.