Introduction

In this blog post, we will explore how to solve the LeetCode problem "802" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i]. A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node). Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order. Example 1: Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]] Output: [2,4,5,6] Explanation: The given graph is shown above. Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them. Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6. Example 2: Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]] Output: [4] Explanation: Only node 4 is a terminal node, and every path starting at node 4 leads to node 4. Constraints: n == graph.length 1 <= n <= 104 0 <= graph[i].length <= n 0 <= graph[i][j] <= n - 1 graph[i] is sorted in a strictly increasing order. The graph may contain self-loops. The number of edges in the graph will be in the range [1, 4 * 104].

Explanation

Here's the breakdown of the solution:

• Identify Terminal Nodes and Reverse the Graph: Start by recognizing terminal nodes (nodes with no outgoing edges). Then, reverse the direction of all edges in the graph. This transforms the problem from finding nodes that lead to terminal nodes to finding nodes that are reachable from terminal nodes in the reversed graph.
• Topological Sort: Perform a topological sort on the reversed graph. Nodes that can be topologically sorted are those reachable from terminal nodes, hence safe nodes. Nodes involved in cycles will not be part of the topological ordering.

• Collect and Sort Safe Nodes: The topologically sorted nodes represent the safe nodes. Sort them in ascending order as required by the problem statement.

• Runtime Complexity: O(N + E), Storage Complexity: O(N + E), where N is the number of nodes and E is the number of edges in the graph.

Code

    from collections import deque

def eventualSafeNodes(graph):
    """
    Finds all eventual safe nodes in a directed graph.

    Args:
        graph: A list of lists representing the graph where graph[i] is a list of nodes
               adjacent to node i.

    Returns:
        A sorted list of all eventual safe nodes.
    """

    n = len(graph)
    reversed_graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for i in range(n):
        for neighbor in graph[i]:
            reversed_graph[neighbor].append(i)  # Reverse the edges
            in_degree[i] += 1  # Calculate in-degree for topological sort

    queue = deque()
    for i in range(n):
        if in_degree[i] == 0:
            queue.append(i)  # Add terminal nodes to the queue

    safe_nodes = []
    while queue:
        node = queue.popleft()
        safe_nodes.append(node)

        for neighbor in reversed_graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    safe_nodes.sort()
    return safe_nodes