All Ancestors of a Node in a Directed Acyclic Graph
01 · Problem
You are given a directed acyclic graph with n nodes numbered 0 to n - 1, and a list edges where edges[i] = [from, to] is a directed edge from from to to.
Node u is an ancestor of node v if there is a path of one or more edges from u to v.
Return a list answer of length n where answer[i] contains every ancestor of node i, sorted in ascending order. A node with no ancestors gets an empty list.
02 · Examples
n = 5, edges = [[0,2],[1,2],[2,3],[3,4],[1,4]]
[[],[],[0,1],[0,1,2],[0,1,2,3]]
Nodes 0 and 1 have no incoming edges. Node 2 is reached from 0 and 1. Node 3 is reached through 2, so its ancestors are 0, 1, 2. Node 4 is reached through 3 and directly from 1, giving 0, 1, 2, 3.
n = 3, edges = []
[[],[],[]]
With no edges, no node has any ancestor.
n = 4, edges = [[3,0],[3,1],[0,2],[1,2]]
[[3],[3],[0,1,3],[]]
Node 3 points to both 0 and 1, which both point to 2. So nodes 0 and 1 each have ancestor 3, node 2 has ancestors 0, 1 and 3, and node 3 has none.
03 · Constraints
- 011 <= n <= 1000
- 020 <= edges.length <= min(2000, n * (n - 1) / 2)
- 03edges[i].length == 2 and 0 <= from, to <= n - 1, from != to
- 04There are no duplicate edges
- 05The graph is acyclic
04 · Optimal complexity
- Time
- O(n * (n + e))
- Space
- O(n^2)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.