All Ancestors of a Node in a Directed Acyclic Graph

Med

#1997Time: O(n * (n + m)), where n is the number of nodes and m is the number of edges. Building the reversed graph takes O(n + m). For each of the n nodes, we perform a traversal (BFS/DFS) which takes O(n + m) in the worst case. Sorting all ancestor lists takes an additional O(n^2 * log n) in the worst case, but this is dominated by the traversal complexity.Space: O(n^2 + m). The reversed adjacency list takes O(n + m) space. The result list `ancestorsList` can store up to O(n^2) elements in total. The `visited` array and queue for BFS in each iteration take O(n) space.1 company

Algorithms

Depth-First Search Breadth-First Search Topological Sort

Data structures

Graph

Companies

Palantir Technologies

Prompt

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:

1 <= n <= 1000
0 <= edges.length <= min(2000, n * (n - 1) / 2)
edges[i].length == 2
0 <= from_i, to_i <= n - 1
from_i != to_i
There are no duplicate edges.
The graph is directed and acyclic.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach finds ancestors for each node independently. For any given node i, its ancestors are all nodes from which i is reachable. This is equivalent to finding all nodes that are reachable from i in a graph where all edge directions are reversed. We can run a separate graph traversal (like BFS or DFS) for each node on this reversed graph.

Algorithm

1. Construct the reversed graph. Create an adjacency list reversedAdj where if u -> v is an edge in the original graph, we add an edge v -> u.
1. Initialize a list of lists ancestors to store the results.
1. For each node i from 0 to n-1:
- a. Perform a Breadth-First Search (BFS) starting from i on the reversedAdj.
- b. Use a visited array to keep track of visited nodes to avoid redundant processing.
- c. All nodes visited during this traversal are ancestors of i. Collect them.
- d. Sort the collected ancestors for node i and add them to the final result list.

Walkthrough

To find the ancestors of a specific node, say v, we need to identify all nodes u such that there exists a path from u to v. A more direct way to frame this is to reverse all the edges of the graph. In this reversed graph, a path from v to u signifies that u is an ancestor of v in the original graph. This method iterates through each node i from 0 to n-1 and, for each one, performs a full graph traversal (BFS is used in the code below) starting from i on the reversed graph. All reachable nodes discovered during this traversal are the ancestors of i. After collecting all ancestors for a node, the list is sorted as required by the problem statement.

1class Solution {2    public List<List<Integer>> getAncestors(int n, int[][] edges) {3        // Build a reversed adjacency list4        List<List<Integer>> revAdj = new ArrayList<>();5        for (int i = 0; i < n; i++) {6            revAdj.add(new ArrayList<>());7        }8        for (int[] edge : edges) {9            revAdj.get(edge[1]).add(edge[0]);10        }11 12        List<List<Integer>> ancestorsList = new ArrayList<>();13        for (int i = 0; i < n; i++) {14            List<Integer> currentAncestors = new ArrayList<>();15            boolean[] visited = new boolean[n];16            Queue<Integer> queue = new LinkedList<>();17            18            queue.add(i);19            visited[i] = true; // Mark start node as visited20 21            while (!queue.isEmpty()) {22                int u = queue.poll();23                // Add to ancestors list only if it's not the start node24                if (u != i) {25                    currentAncestors.add(u);26                }27 28                for (int v : revAdj.get(u)) {29                    if (!visited[v]) {30                        visited[v] = true;31                        queue.add(v);32                    }33                }34            }35            Collections.sort(currentAncestors);36            ancestorsList.add(currentAncestors);37        }38        return ancestorsList;39    }40}

To make the code slightly cleaner, we can run the BFS and collect all visited nodes, then sort and add them. The logic of not adding the start node i to its own ancestor list can be handled by starting the traversal from its parents in the reversed graph, or by simply filtering it out from the result of a traversal starting at i. The BFS for each node explores a part of the graph. Since this is done for every node, many paths might be traversed multiple times, leading to inefficiency.

Complexity

Time

O(n * (n + m)), where n is the number of nodes and m is the number of edges. Building the reversed graph takes O(n + m). For each of the n nodes, we perform a traversal (BFS/DFS) which takes O(n + m) in the worst case. Sorting all ancestor lists takes an additional O(n^2 * log n) in the worst case, but this is dominated by the traversal complexity.

Space

O(n^2 + m). The reversed adjacency list takes O(n + m) space. The result list `ancestorsList` can store up to O(n^2) elements in total. The `visited` array and queue for BFS in each iteration take O(n) space.

Trade-offs

Pros

Conceptually simple and straightforward to implement.
Correctly solves the problem and is efficient enough for the given constraints.

Cons

Inefficient due to redundant computations. The reachability from an ancestor a to a parent p of node i is re-calculated for every child of p.

This approach leverages the Directed Acyclic Graph (DAG) property. We can process nodes in a topological order, which ensures that when we calculate the ancestors for a node u, the ancestors for all its predecessors (parents) have already been fully determined. This allows us to build the ancestor sets dynamically, avoiding redundant computations.

Algorithm

1. Build both a standard adjacency list adj and a reversed adjacency list revAdj. Also, compute the in-degree of each node.
1. Perform a topological sort using Kahn's algorithm to get a valid processing order of nodes.
1. Initialize a list of sets, ancestorSets, to store ancestors for each node. Using a TreeSet automatically handles duplicates and keeps the elements sorted.
1. Iterate through the nodes u in the topological order:
- a. For each direct parent p of u (found using revAdj):
- b. Add p to the ancestor set of u.
- c. Add all ancestors of p (from ancestorSets.get(p)) to the ancestor set of u.
1. Convert the TreeSets to ArrayLists to match the required output format.

Walkthrough

The core idea is that the ancestors of a node u are the union of its direct parents and the ancestors of those parents. ancestors(u) = U_{p in parents(u)} ({p} U ancestors(p)) By processing nodes in a topological order, we guarantee that by the time we process node u, the ancestors(p) for all its parents p are already computed. We first perform a topological sort (Kahn's algorithm is a good choice) to establish the processing order. Then, we iterate through the topologically sorted nodes. For each node u, we look at its parents p (using a pre-built reversed graph). We then merge the parent p itself and all of p's ancestors into u's ancestor set. Using a TreeSet is convenient as it handles sorting and uniqueness automatically.

1class Solution {2    public List<List<Integer>> getAncestors(int n, int[][] edges) {3        List<List<Integer>> adj = new ArrayList<>();4        List<List<Integer>> revAdj = new ArrayList<>();5        int[] inDegree = new int[n];6        for (int i = 0; i < n; i++) {7            adj.add(new ArrayList<>());8            revAdj.add(new ArrayList<>());9        }10 11        for (int[] edge : edges) {12            adj.get(edge[0]).add(edge[1]);13            revAdj.get(edge[1]).add(edge[0]);14            inDegree[edge[1]]++;15        }16 17        Queue<Integer> q = new LinkedList<>();18        for (int i = 0; i < n; i++) {19            if (inDegree[i] == 0) {20                q.add(i);21            }22        }23 24        List<Integer> topoOrder = new ArrayList<>();25        while (!q.isEmpty()) {26            int u = q.poll();27            topoOrder.add(u);28            for (int v : adj.get(u)) {29                inDegree[v]--;30                if (inDegree[v] == 0) {31                    q.add(v);32                }33            }34        }35 36        List<Set<Integer>> ancestorSets = new ArrayList<>();37        for (int i = 0; i < n; i++) {38            ancestorSets.add(new TreeSet<>()); // TreeSet to keep ancestors sorted39        }40 41        for (int u : topoOrder) {42            for (int p : revAdj.get(u)) {43                ancestorSets.get(u).add(p);44                ancestorSets.get(u).addAll(ancestorSets.get(p));45            }46        }47 48        List<List<Integer>> result = new ArrayList<>();49        for (int i = 0; i < n; i++) {50            result.add(new ArrayList<>(ancestorSets.get(i)));51        }52 53        return result;54    }55}

This dynamic programming approach on the DAG is more efficient as it avoids the redundant computations of the simpler traversal-per-node method.

Complexity

Time

O(n*m*log n) or O(n*m). Building graphs and topological sort takes O(n + m). The main work is propagating ancestor sets. For each edge p -> u, we perform a set union. The total work is `sum_{p->u} |ancestors(p)|`. With a `TreeSet`, this is `sum_{p->u} |ancestors(p)| * log(|ancestors(u)|)`. A loose upper bound is O(n*m*log n). If using `HashSet` and sorting at the end, it's closer to O(n*m + n^2*log n). Given the constraints (m <= 2000), this is generally faster than O(n*(n+m)).

Space

O(n^2 + m). The adjacency lists and in-degree array take O(n + m). The `ancestorSets` can store up to O(n^2) elements in total in the worst-case scenario (e.g., a complete DAG).

Trade-offs

Pros

More efficient than the iterative traversal approach, especially for sparse graphs.
Avoids redundant computations by building upon previously computed results using dynamic programming.

Cons

More complex to implement, requiring topological sort and careful propagation of ancestor sets.
Space complexity can be high for dense graphs, although it's the same worst-case as the simpler approach.

Solutions

Solution

1public class Solution {2    private int n;3    private List < int > [] g;4    private IList < IList < int >> ans;5    public IList < IList < int >> GetAncestors(int n, int[][] edges) {6        g = new List < int > [n];7        this.n = n;8        for (int i = 0; i < n; i++) {9            g[i] = new List < int > ();10        }11        foreach(var e in edges) {12            g[e[0]].Add(e[1]);13        }14        ans = new List < IList < int >> ();15        for (int i = 0; i < n; ++i) {16            ans.Add(new List < int > ());17        }18        for (int i = 0; i < n; ++i) {19            BFS(i);20        }21        return ans;22    }23    private void BFS(int s) {24        Queue < int > q = new Queue < int > ();25        q.Enqueue(s);26        bool[] vis = new bool[n];27        vis[s] = true;28        while (q.Count > 0) {29            int i = q.Dequeue();30            foreach(int j in g[i]) {31                if (!vis[j]) {32                    vis[j] = true;33                    q.Enqueue(j);34                    ans[j].Add(s);35                }36            }37        }38    }39}

1class Solution { private int n ; private List < Integer >[] g ; private List < List < Integer >> ans ; public List < List < Integer >> getAncestors ( int n , int [][] edges ) { g = new List [ n ]; this . n = n ; Arrays . setAll ( g , i -> new ArrayList <>()); for ( var e : edges ) { g [ e [ 0 ]]. add ( e [ 1 ]); } ans = new ArrayList <>(); for ( int i = 0 ; i < n ; ++ i ) { ans . add ( new ArrayList <>()); } for ( int i = 0 ; i < n ; ++ i ) { bfs ( i ); } return ans ; } private void bfs ( int s ) { Deque < Integer > q = new ArrayDeque <>(); q . offer ( s ); boolean [] vis = new boolean [ n ]; vis [ s ] = true ; while (! q . isEmpty ()) { int i = q . poll (); for ( int j : g [ i ]) { if (! vis [ j ]) { vis [ j ] = true ; q . offer ( j ); ans . get ( j ). add ( s ); } } } } }

1class Solution { public: vector < vector < int >> getAncestors ( int n , vector < vector < int >>& edges ) { vector < int > g [ n ]; for ( auto & e : edges ) { g [ e [ 0 ]]. push_back ( e [ 1 ]); } vector < vector < int >> ans ( n ); auto bfs = [ & ]( int s ) { queue < int > q ; q . push ( s ); bool vis [ n ]; memset ( vis , 0 , sizeof ( vis )); vis [ s ] = true ; while ( q . size ()) { int i = q . front (); q . pop (); for ( int j : g [ i ]) { if ( ! vis [ j ]) { vis [ j ] = true ; ans [ j ]. push_back ( s ); q . push ( j ); } } } }; for ( int i = 0 ; i < n ; ++ i ) { bfs ( i ); } return ans ; } };

1class Solution : def getAncestors ( self , n : int , edges : List [ List [ int ]]) -> List [ List [ int ]]: def bfs ( s : int ): q = deque ([ s ]) vis = { s } while q : i = q . popleft () for j in g [ i ]: if j not in vis : vis . add ( j ) q . append ( j ) ans [ j ]. append ( s ) g = defaultdict ( list ) for u , v in edges : g [ u ]. append ( v ) ans = [[] for _ in range ( n )] for i in range ( n ): bfs ( i ) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem