Is All Ancestors of a Node in a Directed Acyclic Graph easy or hard?

The problem is classified as Medium on LeetCode. The challenge comes from understanding how to propagate ancestor information across a DAG efficiently. Familiarity with graph traversal, DFS/BFS, and topological sorting makes the solution straightforward.

All Ancestors of a Node in a Directed Acyclic Graph Python/Java solution

Python, Java, and C++ implementations typically build an adjacency list and either run topological sort with ancestor propagation or perform DFS on a reversed graph. Both approaches track visited nodes and collect ancestor sets which are sorted before returning the final result.

How to solve All Ancestors of a Node in a Directed Acyclic Graph in O(n*(n+m))?

Build an adjacency list and compute a topological ordering of the DAG. Maintain a set or list of ancestors for every node. When processing an edge u -> v, insert u into v's ancestor set and merge all ancestors of u into v. Continue this propagation along the topological order so every node receives the full ancestor list.

What is the best approach for All Ancestors of a Node in a Directed Acyclic Graph?

Topological sort with ancestor propagation is the most efficient and commonly expected solution. Process nodes in topological order and propagate ancestor sets along outgoing edges. Each node accumulates its parents and their ancestors. The time complexity is O(n*(n+m)) with O(n^2) space for storing ancestor lists.

Is All Ancestors of a Node in a Directed Acyclic Graph asked at Google/Amazon/Meta?

Graph traversal and DAG ancestor problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations involve dependency graphs, prerequisite tracking, or propagating information through a DAG using topological sort or DFS.

What data structure is used in All Ancestors of a Node in a Directed Acyclic Graph?

The solution uses an adjacency list to represent the directed graph and a set or list for storing ancestors of each node. Algorithms typically rely on depth-first search (DFS), breadth-first search (BFS), or topological sorting with a queue for nodes with zero indegree.

What is the time complexity of All Ancestors of a Node in a Directed Acyclic Graph?

Most optimal implementations run in O(n*(n+m)) time where n is the number of nodes and m is the number of edges. Topological propagation may merge ancestor sets during traversal, while reverse DFS performs a traversal for each node. Space complexity can reach O(n^2) because each node may have up to n ancestors.

Description Hints 2 Solution Video 8:48

2192. All Ancestors of a Node in a Directed Acyclic Graph

Medium62.1% acceptance4 companies

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] = [from_i, to_i] denotes that there is a unidirectional edge from from_i to to_i in the graph.

Return a list answer, where answer[i] is the list of ancestors of the i^th 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: