Find Eventual Safe Locations - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 45 mins
• 🛠️ Topics: Topological Sorting, Graph Representation

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?

• How are terminal locations identified?
  • Terminal locations are nodes with no outgoing edges.
• How do we determine if a node is a safe location?
  • A node is safe if every path from that node leads to a terminal location or another safe node.

HAPPY CASE
Input: city = [
    [1,2], # Location 0
    [2,3], # Location 1
    [5],   # Location 2
    [0],   # Location 3
    [5],   # Location 4
    [],    # Location 5
    []     # Location 6
]
Output: [2,4,5,6]
Explanation: Locations 5 and 6 are terminal. Locations 2 and 4 lead to these terminal nodes.

EDGE CASE
Input: city = [
    [1,2,3,4],
    [1,2],
    [3,4],
    [0,4],
    []
]
Output: [4]
Explanation: Only location 4 is a terminal node.

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

• Graph Representation: Use the graph structure to track the in-degrees of nodes, and perform a reverse topological sort to find all safe locations.
• Kahn’s Algorithm: Apply topological sorting to process nodes with no outgoing edges (terminal nodes) and propagate their safety status to their predecessors.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Perform a reverse topological sort by processing terminal nodes first and marking them as safe. Then, propagate the safety status backward to any nodes that point to terminal nodes, and continue until all safe nodes are found.

1) Initialize an in-degree array to track the number of outgoing edges from each node.
2) Reverse the graph so that edges point to nodes that depend on the current node.
3) Use a queue to process all terminal nodes (nodes with no outgoing edges).
4) For each terminal node, mark it as safe and reduce the in-degree of its predecessors.
5) Continue processing nodes with in-degree 0 until no more nodes can be processed.
6) Return the sorted list of all safe nodes.

⚠️ Common Mistakes

• Forgetting to process the graph in reverse can lead to incorrect results.
• Not handling graphs with cycles properly, which may result in unsafe nodes being marked as safe.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

# Main function to find all eventual safe locations
def eventual_safe_locations(city):
    n = len(city)
    
    # Reverse graph and calculate in-degrees
    reverse_graph = [[] for _ in range(n)]
    in_degree = [0] * n
    
    for node in range(n):
        for neighbor in city[node]:
            reverse_graph[neighbor].append(node)
        in_degree[node] = len(city[node])
    
    # Queue for processing safe nodes (start with terminal nodes)
    queue = deque()
    for node in range(n):
        if in_degree[node] == 0:  # Terminal nodes (no outgoing edges)
            queue.append(node)
    
    # List to store eventual safe locations
    safe_locations = []
    
    while queue:
        safe_node = queue.popleft()
        safe_locations.append(safe_node)
        
        # For each node that points to the current safe node, reduce its in-degree
        for predecessor in reverse_graph[safe_node]:
            in_degree[predecessor] -= 1
            if in_degree[predecessor] == 0:  # If it becomes terminal, add to queue
                queue.append(predecessor)
    
    # Return the safe locations in sorted order
    return sorted(safe_locations)

5: R-eview

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

Example 1:

• Input: city = [ [1,2], [2,3], [5], [0], [5], [], [] ]
• Expected Output: [2,4,5,6]
• Watchlist:
  • Ensure that the reverse graph is built correctly and the terminal nodes are identified.
  • Verify that in-degrees are updated correctly as safe nodes are processed.

6: E-valuate

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

Assume V is the number of nodes (locations) and E is the number of edges (communication lines).

• Time Complexity: O(V + E) because we process each node and edge once.
• Space Complexity: O(V + E) due to the reverse graph and in-degree array.