How do you approach All Ancestors of a Node in a DAG?

Ancestors accumulate along topological order: by the time you process a node, every node before it already knows its own complete ancestor set.

What is the time complexity of All Ancestors of a Node in a DAG?

Time complexity: O(V x E) worst case for the set merges, plus O(V log V) sorting.. Space complexity: O(V^2) worst case for the stored ancestor sets..

What are common mistakes on All Ancestors of a Node in a DAG?

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question. Building the edges the wrong way round - prerequisite pairs are the classic reversal. Seeding the queue with every node instead of only those with zero indegree.

gitGood.dev

← Back to problems

All Ancestors of a Node in a DAG

MediumAlgorithms

Description

You are given a directed acyclic graph with n nodes labelled 0 to n - 1 and a list of edges where edges[i] = [from, to].

Return a list where entry i holds all ancestors of node i, sorted ascending. A node u is an ancestor of v if there is a directed path from u to v. A node is never its own ancestor.

Example 1

Input: n = 5, edges = [[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]]

Example 2

Input: n = 4, edges = [[0,1],[1,2],[2,3]]

Output: [[],[0],[0,1],[0,1,2]]

Example 3

Input: n = 3, edges = []

Output: [[],[],[]]

Constraints

- 1 <= n <= 1000 - 0 <= edges.length <= min(2000, n * (n - 1) / 2) - The graph is guaranteed acyclic with no duplicate edges - Each ancestor list must be sorted ascending and contain no duplicates.

All Ancestors of a Node in a DAG: approach, complexity and pitfalls

A medium topological sort problem, graded against 6 test cases (3 of them hidden).

The pattern: Topological Sort

Ordering a directed acyclic graph so every dependency comes first.

Reach for it when you see: Prerequisites, build order, task scheduling, or "can this be completed?"

If you are stuck

Show the 3-step hint ladder

Ancestors accumulate along topological order: by the time you process a node, every node before it already knows its own complete ancestor set.
Run Kahn's algorithm. When you relax the edge u -> v, merge u's ancestor set into v's AND add u itself.
Use a set per node so repeated paths do not duplicate entries, then sort each set at the end.

The optimal approach

Show the approach: Propagate ancestor sets along the topological order

The brute force runs a traversal from every node - O(V x (V + E)). The better framing: ancestry is transitive, so a node's ancestors are the union of its parents' ancestors plus the parents themselves.

That recurrence needs each parent finished before the child, which is precisely what a topological order guarantees. So run Kahn's algorithm and, when relaxing edge `u -> v`, merge `ancestors[u]` into `ancestors[v]` and add `u`. When `v` finally pops, its set is complete, because every incoming edge was relaxed before its indegree reached zero.

Sets rather than lists matter here: with multiple paths between two nodes (the 5-node example is dense) a list would accumulate duplicates. Sort each set at the end to satisfy the ordering requirement.

This is a good demonstration that topological sort is not only about ordering - it is the schedule that lets any "depends on everything upstream" quantity be computed in one pass. Longest path in a DAG and DAG shortest paths use the identical skeleton.

Time: O(V x E) worst case for the set merges, plus O(V log V) sorting.
Space: O(V^2) worst case for the stored ancestor sets.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Topological Sort mistakes

These apply to the pattern as a whole, not just this problem.

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question.
Building the edges the wrong way round - prerequisite pairs are the classic reversal.
Seeding the queue with every node instead of only those with zero indegree.