What is the time complexity of Minimum Number of Vertices to Reach All Nodes?

The optimal solution has a time complexity of O(n + e).

What data structures are used to solve Minimum Number of Vertices to Reach All Nodes?

This problem uses Graph. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Minimum Number of Vertices to Reach All Nodes?

Insight 1: Nodes with no incoming edges are the key. Any node with an incoming edge can be reached from another node, so the starting set only needs nodes without incoming edges. Insight 2: Since it's a DAG and a unique solution exists, the nodes without incoming edges will be sufficient to reach every other node in the graph.

Which companies ask LeetCode 1557. Minimum Number of Vertices to Reach All Nodes in interviews?

This problem is frequently asked at Airbnb.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Minimum Number of Vertices to Reach All Nodes - LeetCode 1557 Solution

Minimum Number of Vertices to Reach All Nodes - Complete Solution Guide

Minimum Number of Vertices to Reach All Nodes is LeetCode problem 1557, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given a directed acyclic graph , with n vertices numbered from 0 to n-1 , and an array edges where edges[i] = [from i , to i ] represents a directed edge from node from i to node to i . 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 no

Detailed Explanation

The problem asks us to find the smallest set of vertices in a directed acyclic graph (DAG) such that all nodes in the graph are reachable from this set. A crucial detail is that the solution is guaranteed to be unique. Essentially, we need to find the nodes that have no incoming edges, as these nodes must be included in the minimal set to reach all other nodes.

Solution Approach

The solution iterates through the edges and marks all nodes that have incoming edges. Then, it iterates through all nodes and adds any node that wasn't marked (i.e., has no incoming edges) to the result list. This works because any node with an incoming edge is reachable from another node, so we only need the nodes that have no incoming edges to start from.

Step-by-Step Algorithm

Step 1: Initialize a boolean array `has_incoming_edge` of size `n` to `false`. This array will track which nodes have incoming edges.
Step 2: Iterate through the `edges` array. For each edge `[from, to]`, set `has_incoming_edge[to]` to `true`.
Step 3: Initialize an empty list `result` to store the vertices in the smallest set.
Step 4: Iterate through all nodes from `0` to `n-1`. For each node `i`, if `has_incoming_edge[i]` is `false`, add `i` to the `result` list.
Step 5: Return the `result` list.

Key Insights

Insight 1: Nodes with no incoming edges are the key. Any node with an incoming edge can be reached from another node, so the starting set only needs nodes without incoming edges.
Insight 2: Since it's a DAG and a unique solution exists, the nodes without incoming edges will be sufficient to reach every other node in the graph.
Insight 3: No need to perform graph traversals (BFS/DFS). We can determine the result by simply checking which nodes have incoming edges.

Complexity Analysis

Time Complexity: O(n + e)

Space Complexity: O(n)

Topics

This problem involves: Graph.

Companies

Asked at: Airbnb.

Minimum Number of Vertices to Reach All Nodes | LeetCode 1557

Medium

Graph

Time: O(n + e)Space: O(n)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        boolean[] has_incoming_edge = new boolean[n];

        for (List<Integer> edge : edges) {
            has_incoming_edge[edge.get(1)] = true;
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!has_incoming_edge[i]) {
                result.add(i);
            }
        }

        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1557: Minimum Number of Vertices to Reach All Nodes - Detailed explanation and solution approaches.

Topics

Graph

Companies

Airbnb

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1557

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize a boolean array `has_incoming_edge` of size `n` to `false`. This array will track which nodes have incoming edges.
2
Step 2: Iterate through the `edges` array. For each edge `[from, to]`, set `has_incoming_edge[to]` to `true`.
3
Step 3: Initialize an empty list `result` to store the vertices in the smallest set.
4
Step 4: Iterate through all nodes from `0` to `n-1`. For each node `i`, if `has_incoming_edge[i]` is `false`, add `i` to the `result` list.
5
Step 5: Return the `result` list.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n + e)

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is derived from the two iterations: one through the list of edges and one through the list of nodes. The space complexity comes from storing the `has_incoming_edge` boolean array and the result list.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Topological Sort

One could use topological sort to identify the nodes with no incoming edges. However, this would be an overkill, since we only need the initial nodes. Topological sort aims to provide an ordering which isn't required here.

Time: O(n + e)Space: O(n)

Trade-offs: Topological sort is more complex and unnecessary for this problem. It provides more information (ordering of nodes) than needed, making it less efficient.

✨

Key Insights

1Insight 1: Nodes with no incoming edges are the key. Any node with an incoming edge can be reached from another node, so the starting set only needs nodes without incoming edges.
2Insight 2: Since it's a DAG and a unique solution exists, the nodes without incoming edges will be sufficient to reach every other node in the graph.
3Insight 3: No need to perform graph traversals (BFS/DFS). We can determine the result by simply checking which nodes have incoming edges.

📚

Key Terms Explained

For Students

Graph

Nodes connected by edges. Like a social network or city map!

Edge Cases

Edge case 1: Empty graph (n = 0, edges = []). The code correctly handles this by returning an empty list since the loops won't run.
Edge case 2: Graph with no edges (edges = []). The code will correctly return a list of all vertices, as none of them have incoming edges.
Edge case 3: A completely disconnected graph, where each node has no incoming edges. The algorithm will correctly identify all nodes as part of the minimal set.
Edge case 4: A single cycle. Since the graph is defined as a DAG, this isn't strictly an edge case, but the algorithm could potentially have issues if it wasn't truly a DAG. The problem statement guarantees the DAG constraint.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Trying to use graph traversal (BFS/DFS) to find reachable nodes from each vertex. This is unnecessary and less efficient, as we only need to identify nodes with no incoming edges.

✗Common mistake 2: Not understanding the DAG constraint. The solution relies on the fact that cycles don't exist. In a cyclic graph, it's harder to define a minimal set to reach all nodes.

✗Common mistake 3: Incorrectly initializing the `has_incoming_edge` array. In the C solution, it's crucial to initialize the array to all zeros to avoid unexpected behavior due to uninitialized memory.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Dependency resolution in software projects. Identifying which modules don't depend on any other modules allows building them first.

🏦Real-world scenario 2: Task scheduling in project management. Determining which tasks have no prerequisites allows starting them immediately.

🎮Real-world scenario 3: Data pipeline design. Identifying data sources that don't depend on other data sources allows starting the data ingestion process.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Before coding, decide between BFS (shortest path, level-order) and DFS (exhaustive search, connected components). Draw the graph on paper first.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Forgetting to mark nodes as visited, causing infinite loops. Also watch for disconnected components.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 26, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 30

❓

Frequently Asked Questions

When should I use BFS vs DFS for graph problems?

Use BFS for shortest path in unweighted graphs, level-order processing, or when exploring neighbors systematically. Use DFS for exhaustive search, detecting cycles, topological sort, or when you need to explore complete paths. DFS uses less memory for very wide graphs.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Minimum Number of Vertices to Reach All Nodes"?

For this medium-level Graph problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether standard techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?