Scale Engineer

Minimum Number of Vertices to Reach All Nodes

Med
#1433Time: O(n * E), where `n` is the number of vertices and `E` is the number of edges. For each of the `n` vertices, we may iterate through all `E` edges in the worst case.Space: O(k), where `k` is the number of vertices with an in-degree of 0. In the worst case, `k` can be `n`, so the space complexity is O(n) for the result list.1 company
Data structures
Graph
Companies
Airbnb

Prompt

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi.

Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

 

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output: [0,3]
Explanation: It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].

Example 2:

Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
Output: [0,2,3]
Explanation: Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.

 

Constraints:

  • 2 <= n <= 10^5
  • 1 <= edges.length <= min(10^5, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= fromi, toi < n
  • All pairs (fromi, toi) are distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every node in the graph. For each node, it scans the entire list of edges to determine if there is any edge pointing to it. If no such edge is found after checking all edges, the node is considered a source vertex and is added to the result set.

Algorithm

  • Initialize an empty list result.
  • For each vertex i from 0 to n-1:
    • Initialize a boolean flag hasIncomingEdge to false.
    • For each edge [u, v] in the edges list:
      • If v is equal to i, set hasIncomingEdge to true and break the inner loop.
    • After the inner loop, if hasIncomingEdge is false, add i to result.
  • Return result.

Walkthrough

The core idea is to identify nodes that are not destinations in any of the directed edges. These nodes have an in-degree of zero.

  • We initialize an empty list to store the result vertices.
  • We then loop through each vertex i from 0 to n-1.
  • Inside this loop, we assume the current vertex i has no incoming edges by using a flag, say hasIncomingEdge, initialized to false.
  • We then start another loop that iterates through every edge in the edges list.
  • In the inner loop, for each edge [from, to], we check if to is equal to our current vertex i.
  • If we find such an edge, it means vertex i has an incoming edge. We set hasIncomingEdge to true and can break out of the inner loop since we've confirmed it's not a source.
  • After the inner loop finishes, we check the hasIncomingEdge flag. If it's still false, it means no incoming edges were found for vertex i, so we add i to our result list.
  • After checking all vertices from 0 to n-1, the result list will contain all vertices with an in-degree of zero.
import java.util.ArrayList;import java.util.List; class Solution {    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {        List<Integer> result = new ArrayList<>();        for (int i = 0; i < n; i++) {            boolean hasIncomingEdge = false;            for (List<Integer> edge : edges) {                if (edge.get(1) == i) {                    hasIncomingEdge = true;                    break;                }            }            if (!hasIncomingEdge) {                result.add(i);            }        }        return result;    }}

Complexity

Time

O(n * E), where `n` is the number of vertices and `E` is the number of edges. For each of the `n` vertices, we may iterate through all `E` edges in the worst case.

Space

O(k), where `k` is the number of vertices with an in-degree of 0. In the worst case, `k` can be `n`, so the space complexity is O(n) for the result list.

Trade-offs

Pros

  • Simple to understand and implement without requiring any special data structures besides a list.

  • Works directly with the input edge list without needing to build a graph representation like an adjacency list.

Cons

  • Highly inefficient, especially for large graphs. The nested loop structure leads to a time complexity that is too slow for the given constraints.

  • Will likely result in a "Time Limit Exceeded" error on most competitive programming platforms.

Solutions

class Solution {public  List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {    var cnt = new int[n];    for (var e : edges) {      ++cnt[e.get(1)];    }    List<Integer> ans = new ArrayList<>();    for (int i = 0; i < n; ++i) {      if (cnt[i] == 0) {        ans.add(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 →

Next problem