Skip to main content
Talentd

Minimum Number of Vertices to Reach All Nodes - Solution & Explanation

MediumGraph8 min readAsked at: Microsoft, Meta, Airbnb +1
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given a directed graph with n nodes labeled from 0 to n-1 and a list of directed edges. The task is to return the minimum set of starting vertices such that every node in the graph is reachable from at least one of them.

Approach 1: Graph Traversal from Every Node (Brute Force) (Time: O(V * (V + E)), Space: O(V + E))

A straightforward approach is to treat every node as a potential starting vertex. Build an adjacency list and run a traversal such as DFS or BFS from each node to mark which vertices it can reach. Track coverage of all nodes and determine the minimal set of sources required. This works but becomes expensive because each traversal scans the graph again, leading to O(V * (V + E)) time in dense cases. It demonstrates understanding of graph traversal, but it is unnecessary for this specific problem.

Approach 2: Find Nodes with No Incoming Edges (Optimal) (Time: O(V + E), Space: O(V))

The key observation: if a node has at least one incoming edge, it can already be reached from another node. Only nodes with zero indegree cannot be reached by anyone else, so they must be included in the starting set. Iterate through the edge list and compute the indegree of each vertex. After processing all edges, scan the indegree array and collect every node with value 0. These nodes form the smallest set of vertices needed to reach the entire graph.

This works because any node with incoming edges will eventually be reachable from one of the zero‑indegree nodes in a directed acyclic structure of dependencies. The idea is closely related to the starting step of topological sorting, where nodes with zero indegree represent valid starting points.

The algorithm performs a single pass through the edges to compute indegrees and another pass through the vertices to collect answers. That results in linear complexity relative to the graph size. Memory usage stays small since only an integer array of size V is needed.

Recommended for interviews: Interviewers expect the indegree observation. Brute force traversal shows you understand graph reachability, but the optimal approach shows you recognize structural properties of directed graphs and can reduce the problem to a simple indegree scan in O(V + E) time.

Approach 1: Find Nodes with No Incoming Edges

The nodes that have no incoming edges cannot be reached by any other nodes. Thus, these nodes must be included in the result set for ensuring all nodes in the graph are reachable. This is because they can naturally be start points of paths that reach out to other nodes.

We create an array to keep track of nodes with incoming edges. We iterate over all the edges, marking nodes that have incoming edges as true. Finally, we collect all nodes that are not marked as having incoming edges because these are essential to reach all other nodes.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges.
Space Complexity: O(n) for storing incoming edges information.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Find Nodes with No Incoming Edges

Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges.
Space Complexity: O(n) for storing incoming edges information.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph Traversal from Every NodeO(V * (V + E))O(V + E)Conceptual understanding of reachability using DFS/BFS
Nodes with No Incoming Edges (Indegree)O(V + E)O(V)Optimal solution for directed graphs where starting sources must be identified

Video Solution

Minimum Number of Vertices to Reach all Nodes - Leetcode 1557 - Python • NeetCodeIO • 8,040 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Number of Vertices to Reach All Nodes easy or hard?
The problem is rated Medium on LeetCode, but the key insight is simple once you recognize the role of indegree. Identifying nodes with zero incoming edges directly yields the minimal set of starting vertices, making the final implementation short and efficient.
Minimum Number of Vertices to Reach All Nodes Python/Java solution
In Python or Java, create an array of size n initialized to zero. Iterate through the edges and increment the indegree of each destination node. Finally, collect all indices with indegree equal to zero and return them as the result.
How to solve Minimum Number of Vertices to Reach All Nodes in O(n)?
Treat the graph as a directed dependency structure and compute the indegree of every node. Iterate through all edges and increment the indegree of the destination vertex. After processing the graph, return all vertices whose indegree is zero. Those nodes cannot be reached by others and must be included as starting points.
What is the best approach for Minimum Number of Vertices to Reach All Nodes?
The optimal approach is to find all nodes with zero incoming edges (indegree 0). Any node with incoming edges can be reached from another node, so it does not need to be included in the starting set. By computing indegree for each vertex and selecting those with zero indegree, you obtain the minimum set of required starting vertices in O(V + E) time.
Is Minimum Number of Vertices to Reach All Nodes asked at Google/Amazon/Meta?
Graph reachability and indegree-based reasoning appear frequently in interviews at companies like Google, Amazon, and Meta. Problems involving source nodes, topological ordering, or dependency graphs often rely on the same indegree concept used in this problem.
What data structure is used in Minimum Number of Vertices to Reach All Nodes?
The solution primarily uses an integer array (or list) to store indegree values for each vertex. If implementing graph traversal variants, an adjacency list along with BFS or DFS may also be used, but the optimal approach only requires tracking indegree counts.
What is the time complexity of Minimum Number of Vertices to Reach All Nodes?
The optimal solution runs in O(V + E) time, where V is the number of vertices and E is the number of edges. One pass over the edge list calculates indegree values, and another pass over the vertices collects nodes with zero indegree. Space complexity is O(V) for storing the indegree array.

Ready to solve this problem?

Practice Minimum Number of Vertices to Reach All Nodes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Clone Graph

Next

Course Schedule