What is the brute force approach and complexity for All Ancestors of a Node in a DAG?

For each pair (i, j), search from i to see whether it reaches j with time complexity O(N² · (N + E)) and space complexity O(N²).

What is the optimal approach and complexity for All Ancestors of a Node in a DAG?

From every node i, search forward once and add i to the list of every node it reaches with optimal time complexity O(N · (N + E)) and space complexity O(N²).

How do you identify the pattern for All Ancestors of a Node in a DAG?

Look for key signals in the prompt: "ancestors" indicates Every node that can reach this node through any number of arrows, not only the direct parents.; "directed acyclic graph" indicates Arrows have one direction and never form a loop. So 'u reaches v' is a one-way fact, and no node is its own ancestor.; "sorted in ascending order" indicates Process the start nodes in order, so each list is filled in sorted order and no sort is needed..

All Ancestors of a Node in a DAG

Medium·LeetCode #2192Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTopological Sort — DFS order on a DAG (forward reach from each node)

Complexity:O(N² · (N + E))→O(N · (N + E))

Key Insight

Instead of asking about pairs, run one search from each node i. Every node that search reaches has i as an ancestor, so add i to each of their lists. Start the searches in order 0, 1, … , n − 1, so every list fills up in sorted order.

Core Validity Invariant

Node i is an ancestor of w exactly when the search from i reaches w. So each list gets one entry for each such i, and no other entries.

Problem

The nodes of a directed acyclic graph are numbered from 0 to n − 1. You are given edges, where edges[i] = [from, to] is an arrow from from to to. The graph has no cycles.

An ancestor of node v is any node u that can reach v by following arrows, through any number of steps. Direct parents count, and so do parents of parents, and so on.

For every node i, return the list of its ancestors, sorted in ascending order.

Input

n, the number of nodes, and edges, a list of arrows [from, to].

Output

answer[i], the sorted list of all ancestors of node i. The list is empty if no node can reach i.

Example 1

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

Nodes 0, 1 and 2 have no arrows pointing at them. Node 3 has arrows from 0 and 1. Node 6 is reached from 3 and 4, and node 4 is reached from 0 and 2, so the ancestors of 6 are 0, 1, 2, 3 and 4.

Example 2

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]]

Every smaller node points at every bigger node, so node i has the ancestors 0, 1, … up to i − 1.

Constraints

• 1 ≤ n ≤ 1000
• 0 ≤ edges.length ≤ min(2000, n · (n − 1) / 2)
• edges[i].length = 2
• 0 ≤ from, to ≤ n − 1
• from ≠ to
• There are no duplicate edges.
• The graph is directed and acyclic.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
An ancestor is any node that can reach this one through a chain of arrows. Does a direct arrow count, and does a longer chain count?
2.
If I already know the ancestors of node 3, what can I say about the nodes that node 3 points to?
3.
Is it easier to ask who can reach each node, or what each node can reach? Could one answer give me the other?
4.
With n = 1000 there are about half a million pairs. How much work would one search per pair cost?
5.
If I process the start nodes 0, 1, 2, … in order, what do I know about each list as I add to it?

Brute force approach

Idea

Node i is an ancestor of j exactly when i can reach j. So test every pair: run a search from i and check whether j gets reached. If it does, add i to the list of j.

Thinking process

1
The question for each pair is only yes or no: can i reach j?
2
Try every pair. For a fixed j, try each i from 0 to n − 1, and run a search from i that follows the arrows.
3
If the search reaches j, put i in the list of j. Because i goes up in order, the list is already sorted.
4
Check on example 2 for node 2: a search from 0 reaches 2, so 0 is in the list. A search from 1 reaches 2, so 1 is too. A search from 3 does not reach 2, so 3 is not. The list is [0, 1].

Code & Implementation

brute.cpp

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> next(n);
        for (auto& e : edges) next[e[0]].push_back(e[1]);

        // Can node i reach node j? One BFS from i for each pair.
        auto reaches = [&](int i, int j) {
            vector<bool> seen(n, false);
            queue<int> q;
            q.push(i);
            seen[i] = true;
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (int w : next[v]) {
                    if (!seen[w]) {
                        seen[w] = true;
                        q.push(w);
                    }
                }
            }
            return i != j && seen[j];   // i itself is not its own ancestor
        };

        vector<vector<int>> ans(n);
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {   // i goes up, so each list comes out sorted
                if (reaches(i, j)) ans[j].push_back(i);
            }
        }
        return ans;
    }
};

import java.util.*;

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> next = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            next.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            next.get(e[0]).add(e[1]);
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            ans.add(new ArrayList<>());
        }

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < n; i++) {   // i goes up, so each list comes out sorted
                if (reaches(i, j, n, next)) {
                    ans.get(j).add(i);
                }
            }
        }
        return ans;
    }

    // Can node i reach node j? One BFS from i for each pair.
    private boolean reaches(int i, int j, int n, List<List<Integer>> next) {
        if (i == j) return false;   // i itself is not its own ancestor
        boolean[] seen = new boolean[n];
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(i);
        seen[i] = true;
        while (!q.isEmpty()) {
            int v = q.poll();
            for (int w : next.get(v)) {
                if (!seen[w]) {
                    if (w == j) return true;
                    seen[w] = true;
                    q.offer(w);
                }
            }
        }
        return false;
    }
}

from typing import List
from collections import deque

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        next_nodes: List[List[int]] = [[] for _ in range(n)]
        for u, v in edges:
            next_nodes[u].append(v)

        # Can node i reach node j? One BFS from i for each pair.
        def reaches(i: int, j: int) -> bool:
            if i == j:
                return False   # i itself is not its own ancestor
            seen = [False] * n
            q = deque([i])
            seen[i] = True
            while q:
                v = q.popleft()
                for w in next_nodes[v]:
                    if not seen[w]:
                        if w == j:
                            return True
                        seen[w] = True
                        q.append(w)
            return False

        ans: List[List[int]] = [[] for _ in range(n)]
        for j in range(n):
            for i in range(n):   # i goes up, so each list comes out sorted
                if reaches(i, j):
                    ans[j].append(i)
        return ans

export function getAncestors(n: number, edges: number[][]): number[][] {
    const next: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        next[u].push(v);
    }

    // Can node i reach node j? One BFS from i for each pair.
    function reaches(i: number, j: number): boolean {
        if (i === j) return false;   // i itself is not its own ancestor
        const seen: boolean[] = new Array(n).fill(false);
        const q: number[] = [i];
        seen[i] = true;
        let head = 0;
        while (head < q.length) {
            const v = q[head++];
            for (const w of next[v]) {
                if (!seen[w]) {
                    if (w === j) return true;
                    seen[w] = true;
                    q.push(w);
                }
            }
        }
        return false;
    }

    const ans: number[][] = Array.from({ length: n }, () => []);
    for (let j = 0; j < n; j++) {
        for (let i = 0; i < n; i++) {   // i goes up, so each list comes out sorted
            if (reaches(i, j)) ans[j].push(i);
        }
    }
    return ans;
}

Complexity

Time O(N² · (N + E))Space O(N²)

There are N² pairs, and each search can visit N nodes and E arrows. With N = 1000 and E = 2000, that is about 3·10^9 steps. The space is the answer itself, which can hold about N²/2 ancestors.

Optimized approach

Idea

Start from brute force

Brute force runs a separate search for every pair (i, j). One search from i already tells us every node that i reaches, so most of those searches repeat work.

Find the repeated work

The same start node is searched again for every target j, even though one search covers all of them.

Define the state — what variables do I need?

i: The start node of the current search. Every node that the search reaches gets i as an ancestor.
seen[]: Nodes reached by the current search from i. It is reset for every new i.
ans[w]: Ancestors of w found so far. It stays sorted, because i goes from 0 to n − 1.

Define validity

Node i is an ancestor of w exactly when the search from i reaches w. So each list gets one entry for each such i, and no other entries.

Define the transitions — when does each pointer move, and why is it safe?

For i = 0, 1, …, n − 1

Reset seen[]; start a search from i

Each search answers one question: which nodes can i reach?

The search reaches w for the first time

seen[w] = true; ans[w].push_back(i); keep searching from w

i reaches w, so i is an ancestor of w. Another path from i to w would add the same i again, so seen[] skips it.

The search reaches a node that is already seen

Skip it

That node already got i in this search. Adding i again would create a duplicate.

What does the current window add to the answer?

Every pair (i, w) where i reaches w gets exactly one entry in ans[w].

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> next(n);
        for (auto& e : edges) next[e[0]].push_back(e[1]);

        vector<vector<int>> ans(n);
        // Search forward from each node in order, so every list fills up in sorted order.
        for (int i = 0; i < n; i++) {
            vector<bool> seen(n, false);   // reached by this search from i
            vector<int> todo = {i};
            while (!todo.empty()) {
                int v = todo.back();
                todo.pop_back();
                for (int w : next[v]) {
                    if (!seen[w]) {
                        seen[w] = true;
                        ans[w].push_back(i);   // i reaches w, so i is an ancestor of w
                        todo.push_back(w);
                    }
                }
            }
        }
        return ans;
    }
};

import java.util.*;

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> next = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            next.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            next.get(e[0]).add(e[1]);
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ans.add(new ArrayList<>());
        }

        // Search forward from each node in order, so every list fills up in sorted order.
        for (int i = 0; i < n; i++) {
            boolean[] seen = new boolean[n];   // reached by this search from i
            Deque<Integer> todo = new ArrayDeque<>();
            todo.push(i);
            while (!todo.isEmpty()) {
                int v = todo.pop();
                for (int w : next.get(v)) {
                    if (!seen[w]) {
                        seen[w] = true;
                        ans.get(w).add(i);   // i reaches w, so i is an ancestor of w
                        todo.push(w);
                    }
                }
            }
        }
        return ans;
    }
}

from typing import List

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        next_nodes: List[List[int]] = [[] for _ in range(n)]
        for u, v in edges:
            next_nodes[u].append(v)

        ans: List[List[int]] = [[] for _ in range(n)]
        # Search forward from each node in order, so every list fills up in sorted order.
        for i in range(n):
            seen = [False] * n   # reached by this search from i
            todo = [i]
            while todo:
                v = todo.pop()
                for w in next_nodes[v]:
                    if not seen[w]:
                        seen[w] = True
                        ans[w].append(i)   # i reaches w, so i is an ancestor of w
                        todo.append(w)

        return ans

export function getAncestors(n: number, edges: number[][]): number[][] {
    const next: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        next[u].push(v);
    }

    const ans: number[][] = Array.from({ length: n }, () => []);
    // Search forward from each node in order, so every list fills up in sorted order.
    for (let i = 0; i < n; i++) {
        const seen: boolean[] = new Array(n).fill(false);   // reached by this search from i
        const todo: number[] = [i];
        while (todo.length > 0) {
            const v = todo.pop()!;
            for (const w of next[v]) {
                if (!seen[w]) {
                    seen[w] = true;
                    ans[w].push(i);   // i reaches w, so i is an ancestor of w
                    todo.push(w);
                }
            }
        }
    }
    return ans;
}

Complexity

Time O(N · (N + E))Space O(N²)

One search per node, and each search visits at most N nodes and E arrows. The space is the answer itself, which can hold about N²/2 ancestors. The adjacency list and the visited array add O(N + E).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each pair (i, j), search from i to see whether it reaches j	O(N² · (N + E))	O(N²)
Optimal	From every node i, search forward once and add i to the list of every node it reaches	O(N · (N + E))	O(N²)

Why does this belong to this pattern?

Clues in the problem statement

“ancestors”Every node that can reach this node through any number of arrows, not only the direct parents.
“directed acyclic graph”Arrows have one direction and never form a loop. So 'u reaches v' is a one-way fact, and no node is its own ancestor.
“sorted in ascending order”Process the start nodes in order, so each list is filled in sorted order and no sort is needed.

directed acyclic graph+reach through any number of arrows+one search from each node, pushing forward→Topological Sort — DFS order on a DAG (forward reach from each node)

This is the first question of the DFS order / DAG DP group. The graph has no loops, so 'i reaches w' is a fixed, one-way fact. The trick is to flip the question: instead of asking who can reach w (backwards, from many places), let each node push itself forward onto everything it reaches. Loud and Rich and Longest Increasing Path go one step further and reuse answers with memoised DFS.

Don't make this mistake

Counting only the direct arrows

✗ for (auto& e : edges) ans[e[1]].push_back(e[0]); // only direct parents

✓ // add i to every node that the search from i reaches

This is the pattern-confusion trap: an ancestor is anyone who can reach the node, not only its direct parents. On the dry-run graph, node 6 has direct parents 3 and 4 only, but its ancestors are 0, 1, 2, 3 and 4. Node 0 reaches 6 through 3 (0 → 3 → 6) and through 4 (0 → 4 → 6). Node 5 gets [3] instead of [0, 1, 3].

Merging the parents' lists without removing duplicates

✗ for (int p : parents[w]) { ans[w].insert(ans[w].end(), ans[p].begin(), ans[p].end()); ans[w].push_back(p); } // no dedup, no sort

✓ // forward search: each i is added once per list, in increasing order of i

Merging parents is a tempting shortcut. On the dry run, node 6 has parents 3 and 4. Merging gives [0, 1, 3] + [0, 2, 4] = [0, 1, 3, 0, 2, 4]. The 0 appears twice, and the list is not sorted. Removing duplicates and sorting would fix it, but the forward search never creates the problem.

Swapping the direction: descendants instead of ancestors

✗ // inside the search from i, when w is first reached: ans[i].push_back(w); // what i reaches

✓ // inside the search from i, when w is first reached: ans[w].push_back(i); // i is an ancestor of w

The wrong line fills the list of i with the nodes that i reaches, which are its descendants. On the dry run, node 0 would get [3, 4, 5, 6, 7] instead of []. Node 0 has no ancestors, since nothing points at it.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.

LLD Practice

Task Scheduler & Workflow Orchestrator

Resolving DAG build pipelines and asynchronous task dependency resolution.

Explore Track

C++ Internals

Static vs Global Linkage & Init Order Fiasco

Why compilers resolve static global variables as a DAG to prevent runtime crashes.

Explore Track

Loud and Rich