Introduction

In this blog post, we will explore how to solve the LeetCode problem "2192" 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

You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive). You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph. Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order. A node u is an ancestor of another node v if u can reach v via a set of edges. Example 1: Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]] Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]] Explanation: The above diagram represents the input graph. - Nodes 0, 1, and 2 do not have any ancestors. - Node 3 has two ancestors 0 and 1. - Node 4 has two ancestors 0 and 2. - Node 5 has three ancestors 0, 1, and 3. - Node 6 has five ancestors 0, 1, 2, 3, and 4. - Node 7 has four ancestors 0, 1, 2, and 3. Example 2: Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]] Explanation: The above diagram represents the input graph. - Node 0 does not have any ancestor. - Node 1 has one ancestor 0. - Node 2 has two ancestors 0 and 1. - Node 3 has three ancestors 0, 1, and 2. - Node 4 has four ancestors 0, 1, 2, and 3. Constraints: 1 <= n <= 1000 0 <= edges.length <= min(2000, n * (n - 1) / 2) edges[i].length == 2 0 <= fromi, toi <= n - 1 fromi != toi There are no duplicate edges. The graph is directed and acyclic.

Explanation

Here's the solution approach, complexity analysis, and Python code:

• High-Level Approach:

  • Use Depth First Search (DFS) to traverse the graph.
  • Maintain a visited set for each node to store its ancestors. We use sets instead of lists to avoid duplicate ancestor entries and for efficient lookups when building the ancestor list for a node.
  • For each node, perform DFS to find all reachable nodes (its descendants). Add the ancestors found during DFS to the visited set for each descendant.

• Complexity Analysis:

  • Runtime Complexity: O(n * (n + m)), where n is the number of nodes and m is the number of edges. The outer loop iterates n times, and DFS takes O(n + m) time in the worst case. Since in the worst case m = O(n^2), the complexity can be rewritten as O(n^3)
  • Storage Complexity: O(n^2) in the worst case, where each node could potentially have all other nodes as ancestors.

Code

    def getAncestors(n: int, edges: list[list[int]]) -> list[list[int]]:
    """
    Finds the ancestors of each node in a DAG.

    Args:
        n: The number of nodes in the DAG.
        edges: A list of edges, where edges[i] = [fromi, toi].

    Returns:
        A list of lists, where answer[i] is the list of ancestors of the ith node, sorted in ascending order.
    """

    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)

    ancestors = [set() for _ in range(n)]

    def dfs(node, ancestor, visited):
        """
        Performs Depth First Search to find all reachable nodes from a given node.
        """
        visited.add(ancestor)
        for neighbor in graph[node]:
            ancestors[neighbor].add(ancestor)  # Add ancestor of node to neighbor's ancestor set
            dfs(neighbor, ancestor, visited)

    for i in range(n):
        visited = set()
        for j in graph[i]:
             ancestors[j].add(i)
             dfs(j,i, visited)


    result = [sorted(list(ancestors[i])) for i in range(n)]
    return result