Expanding Flight Offerings - codepath/compsci_guides GitHub Wiki

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

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, 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 the adjacency dictionary flights represent?
    • A: Each key is an airport, and the value is a list of airports that have direct flights from that key airport.
  • Q: Are the flight paths bidirectional?
    • A: Yes, if there is a flight from i to j, then there is also a flight from j to i.
  • Q: What should be returned?
    • A: The minimum number of flights (edges) that need to be added to make sure there is a path from any airport to every other airport.
HAPPY CASE
Input: 
flights = {
    'JFK': ['LAX', 'SFO'],
    'LAX': ['JFK', 'SFO'],
    'SFO': ['JFK', 'LAX'],
    'ORD': ['ATL'],
    'ATL': ['ORD']
}

Output:
1
Explanation: The airports form two connected components: {'JFK', 'LAX', 'SFO'} and {'ORD', 'ATL'}. Only one flight is needed to connect the two components.

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

  • Depth First Search (DFS): DFS can be used to explore all airports in each connected component, allowing us to count how many disconnected components there are.
  • Breadth First Search (BFS): BFS could also be used, but DFS is more typical when finding connected components in undirected graphs.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We need to find the number of connected components in the graph. The minimum number of flights required to connect all airports will be equal to the number of components minus one. Use DFS to explore each component and count how many components exist.

1) Build an undirected graph from the `flights` dictionary. Make sure all airports are properly connected in both directions.
2) Initialize a `visited` set to track the airports that have already been explored.
3) Use DFS to traverse through each connected component.
   a) For each unvisited airport, perform a DFS to explore all airports in its component.
   b) Increment the number of components whenever a new component is found.
4) The minimum number of flights needed to connect all components is `(number of components - 1)`.

⚠️ Common Mistakes

  • Forgetting to connect airports bidirectionally.
  • Not correctly counting the number of connected components.

4: I-mplement

Implement the code to solve the algorithm.

def min_flights_to_expand(flights):
    # Step 1: Build an undirected graph from the flights dictionary
    graph = {}
    for airport in flights:
        if airport not in graph:
            graph[airport] = set()
        for destination in flights[airport]:
            graph[airport].add(destination)
            if destination not in graph:
                graph[destination] = set()
            graph[destination].add(airport)
    
    # Step 2: Use DFS to find connected components
    def dfs(airport, visited):
        stack = [airport]
        while stack:
            node = stack.pop()
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
    
    visited = set()
    num_components = 0

    # Step 3: Traverse through each airport and find new connected components
    for airport in graph:
        if airport not in visited:
            # New component found, run DFS
            visited.add(airport)
            dfs(airport, visited)
            num_components += 1

    # Step 4: The minimum number of flights needed is (number of components - 1)
    return num_components - 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:
flights = {
    'JFK': ['LAX', 'SFO'],
    'LAX': ['JFK', 'SFO'],
    'SFO': ['JFK', 'LAX'],
    'ORD': ['ATL'],
    'ATL': ['ORD']
}

print(min_flights_to_expand(flights))  # Expected output: 1
  • Output:
1

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). We build the graph and then use DFS to explore all vertices and edges.
  • Space Complexity: O(V + E) for storing the graph and visited set.