Finding All Reachable Destinations II - codepath/compsci_guides GitHub Wiki

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

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)

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 represent?
    • A: Each key in the dictionary is a city, and the corresponding value is a list of cities reachable from that city by a direct flight.
  • Q: What traversal method is used?
    • A: We need to use Depth First Search (DFS) to explore all reachable destinations.
  • Q: What order should destinations be returned in?
    • A: Destinations should be returned in the order they are visited during the DFS.
HAPPY CASE
Input: 
flights = {
    ""Tokyo"": [""Sydney""],
    ""Sydney"": [""Tokyo"", ""Beijing""],
    ""Beijing"": [""Mexico City"", ""Helsinki""],
    ""Helsinki"": [""Cairo"", ""New York""],
    ""Cairo"": [""Helsinki"", ""Reykjavik""],
    ""Reykjavik"": [""Cairo"", ""New York""],
    ""Mexico City"": [""Sydney""]
}
start = ""Beijing""
Output: ['Beijing', 'Mexico City', 'Sydney', 'Tokyo', 'Helsinki', 'Cairo', 'Reykjavik', 'New York']
Explanation: Starting from Beijing, the DFS visits all reachable destinations in the order they are visited.

EDGE CASE
Input: 
flights = {
    ""Tokyo"": [""Sydney""],
    ""Sydney"": [""Tokyo""]
}
start = ""Tokyo""
Output: ['Tokyo', 'Sydney']
Explanation: From Tokyo, the DFS explores Sydney as the only destination and returns both airports.

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:

  • Depth First Search (DFS): This is the most appropriate traversal strategy for this problem, where we visit all possible destinations in a depth-first manner.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS to explore all reachable destinations from the start city, visiting each destination as deeply as possible before backtracking. We will keep track of visited cities to avoid revisiting the same city.

1) Create a set `visited` to keep track of visited cities.
2) Create a list `result` to store the order of visited cities.
3) Define a recursive helper function `dfs(airport)`:
   a) Add `airport` to `visited`.
   b) Append `airport` to `result`.
   c) For each `neighbor` of the current airport, if the neighbor has not been visited, recursively call `dfs(neighbor)`.
4) Call the helper function `dfs(start)` to start the DFS traversal from the `start` city.
5) Return the `result` list containing all reachable cities.

⚠️ Common Mistakes

  • Not marking cities as visited, which can lead to infinite loops or revisiting the same city multiple times.
  • Forgetting to handle the case where there are no outgoing flights from the start city.

4: I-mplement

Implement the code to solve the algorithm.

def get_all_destinations(flights, start):
    visited = set()  # Set to keep track of visited airports
    result = []  # List to store the order of visited airports

    # Recursive DFS function
    def dfs(airport):
        # Mark the airport as visited and add it to the result
        visited.add(airport)
        result.append(airport)

        # Visit each neighbor (destination) that hasn't been visited yet
        for neighbor in flights.get(airport, []):
            if neighbor not in visited:
                dfs(neighbor)

    # Start the DFS from the given starting airport
    dfs(start)

    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:
flights = {
    ""Tokyo"": [""Sydney""],
    ""Sydney"": [""Tokyo"", ""Beijing""],
    ""Beijing"": [""Mexico City"", ""Helsinki""],
    ""Helsinki"": [""Cairo"", ""New York""],
    ""Cairo"": [""Helsinki"", ""Reykjavik""],
    ""Reykjavik"": [""Cairo"", ""New York""],
    ""Mexico City"": [""Sydney""]
}
print(get_all_destinations(flights, ""Beijing""))

  • Output: ['Beijing', 'Mexico City', 'Sydney', 'Tokyo', 'Helsinki', 'Cairo', 'Reykjavik', 'New York']

  • Input:

flights = {
    ""Tokyo"": [""Sydney""],
    ""Sydney"": [""Tokyo""]
}
print(get_all_destinations(flights, ""Tokyo""))
  • Output: ['Tokyo', 'Sydney']

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 cities (vertices) and E is the number of flights (edges). Each city and each flight is visited once.
  • Space Complexity: O(V) for storing the visited set and the recursion stack in the worst case.