Minimum Number of Vertices to Reach All Nodes

🎯

Minimum Number of Vertices to Reach All Nodes

mediumGRAPHAmazonGoogle

Imagine you want to send a message to every employee in a company, but you can only start by directly contacting a few key people. Who should you pick so that everyone eventually hears the message?

💡 This problem asks for the smallest set of starting points in a directed graph so that all nodes are reachable. Beginners often struggle because they try complex traversals or miss the insight that only nodes with zero incoming edges need to be chosen.

📋

Problem Statement

Given a directed acyclic graph (DAG) with n vertices labeled from 0 to n-1, and a list of edges where edges[i] = [from_i, to_i], find the minimum set of vertices from which all nodes in the graph are reachable. Return any such set of vertices.

1 ≤ n ≤ 10^51 ≤ edges.length ≤ 10^5edges[i].length == 20 ≤ from_i, to_i < nAll edges are uniqueThe graph is a DAG (no cycles)

💡

Example

Input"n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]"

Output[0,3]

Vertices 0 and 3 have zero in-degree and starting from them, all nodes can be reached.

• Graph with no edges → all nodes must be chosen
• Graph where all nodes except one have incoming edges → only one node chosen
• Graph with multiple disconnected components → one zero in-degree node per component
• Graph with a single node → that node is the answer

⚠️

Common Mistakes

Trying to find nodes that reach all others by checking reachability from each node

Code runs too slowly and times out on large inputs

✅ Use in-degree counting to identify zero in-degree nodes instead

Including nodes with non-zero in-degree in the result

Result is not minimal and may be rejected by interviewer

✅ Only include nodes with zero in-degree

Not handling disconnected components properly

Misses some zero in-degree nodes, so not all nodes are reachable

✅ Count in-degree for all nodes and include all zero in-degree nodes from all components

Assuming graph is not a DAG and trying to use topological sort without cycle detection

Algorithm may fail or produce incorrect results if cycles exist

✅ Confirm problem states DAG or add cycle detection if needed

Using BFS/DFS from zero in-degree nodes to verify reachability unnecessarily

Unneeded complexity and runtime increase

✅ Trust the zero in-degree node property for DAGs as minimal set

🧠

Brute Force (Check Reachability from Every Node)

💡 This approach exists to build intuition by trying all possible starting nodes and checking if they can reach all nodes. It is inefficient but helps understand the problem deeply.

Intuition

Try starting a DFS or BFS from each node and see if all nodes are reachable. Collect nodes that can reach all others.

Algorithm

1. For each node from 0 to n-1:
2. Perform DFS/BFS to find all reachable nodes.
3. If the reachable set includes all nodes, add this node to the candidate set.
4. Return the minimal candidate set found (or all such nodes).

💡 This algorithm is straightforward but inefficient because it repeats expensive traversals for every node.

</>

Code

from collections import deque

def findSmallestSetOfVertices(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)

    def bfs(start):
        visited = set()
        queue = deque([start])
        while queue:
            node = queue.popleft()
            if node not in visited:
                visited.add(node)
                for nei in graph[node]:
                    if nei not in visited:
                        queue.append(nei)
        return visited

    result = []
    for i in range(n):
        reachable = bfs(i)
        if len(reachable) == n:
            result.append(i)
    return result

# Example usage:
if __name__ == '__main__':
    n = 6
    edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
    print(findSmallestSetOfVertices(n, edges))

Line Notes

graph = [[] for _ in range(n)]Initialize adjacency list for graph representation

for u, v in edges:Build graph edges for traversal

def bfs(start):Define BFS to find reachable nodes from start

visited = set()Track visited nodes to avoid cycles and repeated visits

queue = deque([start])Initialize queue with start node for BFS

while queue:Process nodes in BFS order

node = queue.popleft()Get current node to explore neighbors

if node not in visited:Process node only if not visited

for nei in graph[node]:Explore all neighbors of current node

if nei not in visited:Add unvisited neighbors to queue

result = []Store nodes that can reach all others

for i in range(n):Check reachability from every node

reachable = bfs(i)Get reachable nodes from node i

if len(reachable) == n:If all nodes reachable, add to result

return resultReturn all nodes that can reach entire graph

import java.util.*;

public class Solution {
    public static List<Integer> findSmallestSetOfVertices(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) graph.get(edge[0]).add(edge[1]);

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (bfs(i, graph, n)) result.add(i);
        }
        return result;
    }

    private static boolean bfs(int start, List<List<Integer>> graph, int n) {
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        int count = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (!visited[node]) {
                visited[node] = true;
                count++;
                for (int nei : graph.get(node)) {
                    if (!visited[nei]) queue.offer(nei);
                }
            }
        }
        return count == n;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] edges = {{0,1},{0,2},{2,5},{3,4},{4,2}};
        System.out.println(findSmallestSetOfVertices(n, edges));
    }

Line Notes

List<List<Integer>> graph = new ArrayList<>();Initialize adjacency list for graph

for (int[] edge : edges)Build graph edges

List<Integer> result = new ArrayList<>();Store nodes that reach all others

for (int i = 0; i < n; i++)Check reachability from each node

if (bfs(i, graph, n))If BFS from i reaches all nodes, add i

boolean[] visited = new boolean[n];Track visited nodes in BFS

Queue<Integer> queue = new LinkedList<>();Initialize BFS queue

queue.offer(start);Start BFS from node

while (!queue.isEmpty())Process BFS queue

if (!visited[node])Process unvisited nodes

count++Count how many nodes visited

return count == n;Check if all nodes reached

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
    vector<vector<int>> graph(n);
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
    }

    vector<int> result;
    for (int i = 0; i < n; i++) {
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(i);
        int count = 0;
        while (!q.empty()) {
            int node = q.front(); q.pop();
            if (!visited[node]) {
                visited[node] = true;
                count++;
                for (int nei : graph[node]) {
                    if (!visited[nei]) q.push(nei);
                }
            }
        }
        if (count == n) result.push_back(i);
    }
    return result;
}

int main() {
    int n = 6;
    vector<vector<int>> edges = {{0,1},{0,2},{2,5},{3,4},{4,2}};
    vector<int> res = findSmallestSetOfVertices(n, edges);
    for (int v : res) cout << v << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<vector<int>> graph(n);Initialize adjacency list

for (auto& e : edges)Build graph edges

vector<int> result;Store nodes that reach all others

for (int i = 0; i < n; i++)Check reachability from each node

vector<bool> visited(n, false);Track visited nodes for BFS

queue<int> q;Initialize BFS queue

q.push(i);Start BFS from node i

while (!q.empty())Process BFS queue

if (!visited[node])Process unvisited nodes

count++Count visited nodes

if (count == n) result.push_back(i);If all nodes reached, add i

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

    function bfs(start) {
        const visited = new Set();
        const queue = [start];
        while (queue.length > 0) {
            const node = queue.shift();
            if (!visited.has(node)) {
                visited.add(node);
                for (const nei of graph[node]) {
                    if (!visited.has(nei)) queue.push(nei);
                }
            }
        }
        return visited;
    }

    const result = [];
    for (let i = 0; i < n; i++) {
        const reachable = bfs(i);
        if (reachable.size === n) result.push(i);
    }
    return result;
}

// Example usage:
const n = 6;
const edges = [[0,1],[0,2],[2,5],[3,4],[4,2]];
console.log(findSmallestSetOfVertices(n, edges));

Line Notes

const graph = Array.from({length: n}, () => []);Initialize adjacency list

for (const [u, v] of edges)Build graph edges

function bfs(start)Define BFS to find reachable nodes

const visited = new Set();Track visited nodes

const queue = [start];Initialize BFS queue

while (queue.length > 0)Process BFS queue

const node = queue.shift();Get current node

if (!visited.has(node))Process unvisited nodes

for (const nei of graph[node])Explore neighbors

if (!visited.has(nei)) queue.push(nei);Add unvisited neighbors to queue

const result = [];Store nodes that reach all others

for (let i = 0; i < n; i++)Check reachability from each node

const reachable = bfs(i);Get reachable nodes from node i

if (reachable.size === n) result.push(i);If all nodes reachable, add to result

return result;Return nodes that reach all others

⏱

Complexity

TimeO(n * (n + e))

SpaceO(n + e)

For each of the n nodes, we perform a BFS/DFS that can visit up to all n nodes and edges e, resulting in O(n*(n+e)) time.

💡 For n=1000 and e=2000, this means about 3 million operations, which is too slow for large inputs.

Interview Verdict: TLE

This brute force approach is too slow for large graphs but helps understand the problem and why we need a better method.

🧠

Better Approach (Use In-degree Counting)

💡 This approach leverages the insight that only nodes with zero in-degree need to be chosen to reach all nodes, drastically reducing complexity.

Intuition

Nodes with incoming edges can be reached from other nodes, so only nodes with zero incoming edges must be included in the answer.

Algorithm

1. Initialize an array to count in-degree for each node.
2. Iterate over edges and increment in-degree of destination nodes.
3. Collect all nodes with zero in-degree into the result list.
4. Return the result list.

💡 This algorithm is simple and efficient because it avoids repeated traversals by using in-degree counts.

</>

Code

def findSmallestSetOfVertices(n, edges):
    in_degree = [0] * n
    for u, v in edges:
        in_degree[v] += 1
    result = [i for i in range(n) if in_degree[i] == 0]
    return result

# Example usage:
if __name__ == '__main__':
    n = 6
    edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
    print(findSmallestSetOfVertices(n, edges))

Line Notes

in_degree = [0] * nInitialize in-degree counts to zero for all nodes

for u, v in edges:Iterate over edges to count incoming edges

in_degree[v] += 1Increment in-degree for destination node

result = [i for i in range(n) if in_degree[i] == 0]Collect nodes with zero in-degree

return resultReturn minimal set of vertices to reach all nodes

import java.util.*;

public class Solution {
    public static List<Integer> findSmallestSetOfVertices(int n, int[][] edges) {
        int[] inDegree = new int[n];
        for (int[] edge : edges) {
            inDegree[edge[1]]++;
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) result.add(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] edges = {{0,1},{0,2},{2,5},{3,4},{4,2}};
        System.out.println(findSmallestSetOfVertices(n, edges));
    }
}

Line Notes

int[] inDegree = new int[n];Initialize in-degree array

for (int[] edge : edges)Count incoming edges for each node

inDegree[edge[1]]++;Increment in-degree for destination node

List<Integer> result = new ArrayList<>();Prepare list for zero in-degree nodes

if (inDegree[i] == 0) result.add(i);Add nodes with zero in-degree to result

#include <iostream>
#include <vector>
using namespace std;

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
    vector<int> inDegree(n, 0);
    for (auto& e : edges) {
        inDegree[e[1]]++;
    }
    vector<int> result;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) result.push_back(i);
    }
    return result;
}

int main() {
    int n = 6;
    vector<vector<int>> edges = {{0,1},{0,2},{2,5},{3,4},{4,2}};
    vector<int> res = findSmallestSetOfVertices(n, edges);
    for (int v : res) cout << v << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<int> inDegree(n, 0);Initialize in-degree counts

for (auto& e : edges)Count incoming edges for each node

inDegree[e[1]]++;Increment in-degree for destination node

vector<int> result;Store zero in-degree nodes

if (inDegree[i] == 0) result.push_back(i);Add zero in-degree nodes to result

function findSmallestSetOfVertices(n, edges) {
    const inDegree = new Array(n).fill(0);
    for (const [u, v] of edges) {
        inDegree[v]++;
    }
    const result = [];
    for (let i = 0; i < n; i++) {
        if (inDegree[i] === 0) result.push(i);
    }
    return result;
}

// Example usage:
const n = 6;
const edges = [[0,1],[0,2],[2,5],[3,4],[4,2]];
console.log(findSmallestSetOfVertices(n, edges));

Line Notes

const inDegree = new Array(n).fill(0);Initialize in-degree array

for (const [u, v] of edges)Count incoming edges

inDegree[v]++;Increment in-degree for destination node

const result = [];Prepare result array

if (inDegree[i] === 0) result.push(i);Add zero in-degree nodes to result

⏱

Complexity

TimeO(n + e)

SpaceO(n)

We count in-degree in one pass over edges (O(e)) and then scan nodes once (O(n)), total O(n+e).

💡 For n=100000 and e=100000, this approach is efficient and runs quickly.

Interview Verdict: Accepted

This approach is optimal and accepted for large inputs, demonstrating the power of problem insight.

🧠

Alternative Approach (Topological Sort Based)

💡 This approach uses topological sorting to identify sources (zero in-degree nodes) explicitly, reinforcing understanding of DAG properties.

Intuition

Perform a topological sort and collect all nodes that have zero in-degree at the start, as these are the minimal set to reach all nodes.

Algorithm

1. Compute in-degree for all nodes.
2. Initialize a queue with all zero in-degree nodes.
3. Perform topological sort by removing nodes from queue and decrementing in-degree of neighbors.
4. Return the initial zero in-degree nodes as the minimal set.

💡 This algorithm explicitly uses topological sort mechanics to find the minimal set, which is useful in DAG-related problems.

</>

Code

from collections import deque

def findSmallestSetOfVertices(n, edges):
    in_degree = [0] * n
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = list(queue)

    while queue:
        node = queue.popleft()
        for nei in graph[node]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)

    return result

# Example usage:
if __name__ == '__main__':
    n = 6
    edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
    print(findSmallestSetOfVertices(n, edges))

Line Notes

in_degree = [0] * nInitialize in-degree counts

graph = [[] for _ in range(n)]Initialize adjacency list

for u, v in edges:Build graph and count in-degree

queue = deque([i for i in range(n) if in_degree[i] == 0])Initialize queue with zero in-degree nodes

result = list(queue)Store initial zero in-degree nodes as result

while queue:Process nodes in topological order

node = queue.popleft()Remove node from queue

for nei in graph[node]:Visit neighbors

in_degree[nei] -= 1Decrement in-degree of neighbor

if in_degree[nei] == 0:Add neighbor to queue if zero in-degree

import java.util.*;

public class Solution {
    public static List<Integer> findSmallestSetOfVertices(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        int[] inDegree = new int[n];
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            inDegree[edge[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
                result.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int nei : graph.get(node)) {
                inDegree[nei]--;
                if (inDegree[nei] == 0) queue.offer(nei);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] edges = {{0,1},{0,2},{2,5},{3,4},{4,2}};
        System.out.println(findSmallestSetOfVertices(n, edges));
    }
}

Line Notes

List<List<Integer>> graph = new ArrayList<>();Initialize adjacency list

int[] inDegree = new int[n];Initialize in-degree array

for (int[] edge : edges)Build graph and count in-degree

Queue<Integer> queue = new LinkedList<>();Initialize queue for topological sort

if (inDegree[i] == 0)Add zero in-degree nodes to queue and result

while (!queue.isEmpty())Process nodes in topological order

int node = queue.poll();Remove node from queue

for (int nei : graph.get(node))Visit neighbors

inDegree[nei]--;Decrement in-degree of neighbor

if (inDegree[nei] == 0) queue.offer(nei);Add neighbor to queue if zero in-degree

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
    vector<vector<int>> graph(n);
    vector<int> inDegree(n, 0);
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
        inDegree[e[1]]++;
    }

    queue<int> q;
    vector<int> result;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
            result.push_back(i);
        }
    }

    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (int nei : graph[node]) {
            inDegree[nei]--;
            if (inDegree[nei] == 0) q.push(nei);
        }
    }

    return result;
}

int main() {
    int n = 6;
    vector<vector<int>> edges = {{0,1},{0,2},{2,5},{3,4},{4,2}};
    vector<int> res = findSmallestSetOfVertices(n, edges);
    for (int v : res) cout << v << ' ';
    cout << endl;
    return 0;
}

Line Notes

vector<vector<int>> graph(n);Initialize adjacency list

vector<int> inDegree(n, 0);Initialize in-degree counts

for (auto& e : edges)Build graph and count in-degree

queue<int> q;Initialize queue for topological sort

if (inDegree[i] == 0)Add zero in-degree nodes to queue and result

while (!q.empty())Process nodes in topological order

int node = q.front(); q.pop();Remove node from queue

for (int nei : graph[node])Visit neighbors

inDegree[nei]--;Decrement in-degree of neighbor

if (inDegree[nei] == 0) q.push(nei);Add neighbor to queue if zero in-degree

function findSmallestSetOfVertices(n, edges) {
    const graph = Array.from({length: n}, () => []);
    const inDegree = new Array(n).fill(0);
    for (const [u, v] of edges) {
        graph[u].push(v);
        inDegree[v]++;
    }

    const queue = [];
    const result = [];
    for (let i = 0; i < n; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
            result.push(i);
        }
    }

    while (queue.length > 0) {
        const node = queue.shift();
        for (const nei of graph[node]) {
            inDegree[nei]--;
            if (inDegree[nei] === 0) queue.push(nei);
        }
    }

    return result;
}

// Example usage:
const n = 6;
const edges = [[0,1],[0,2],[2,5],[3,4],[4,2]];
console.log(findSmallestSetOfVertices(n, edges));

Line Notes

const graph = Array.from({length: n}, () => []);Initialize adjacency list

const inDegree = new Array(n).fill(0);Initialize in-degree array

for (const [u, v] of edges)Build graph and count in-degree

const queue = [];Initialize queue for topological sort

if (inDegree[i] === 0)Add zero in-degree nodes to queue and result

while (queue.length > 0)Process nodes in topological order

const node = queue.shift();Remove node from queue

for (const nei of graph[node])Visit neighbors

inDegree[nei]--;Decrement in-degree of neighbor

if (inDegree[nei] === 0) queue.push(nei);Add neighbor to queue if zero in-degree

⏱

Complexity

TimeO(n + e)

SpaceO(n + e)

Topological sort requires building adjacency list and processing all edges and nodes once, O(n+e).

💡 This approach is efficient and uses standard graph algorithms, suitable for large inputs.

Interview Verdict: Accepted

This approach is optimal and demonstrates understanding of DAG properties and topological sorting.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, use the in-degree counting approach because it is simple, efficient, and accepted.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*(n+e))	O(n+e)	Yes (deep recursion if DFS used)	N/A	Mention only - never code due to inefficiency
2. In-degree Counting	O(n+e)	O(n)	No	N/A	Code this approach for optimal solution
3. Topological Sort Based	O(n+e)	O(n+e)	No	N/A	Good alternative to explain DAG properties

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to check reachability from every node.Step 3: Explain why brute force is inefficient and introduce the in-degree counting insight.Step 4: Code the in-degree counting solution and test with examples.Step 5: Optionally discuss topological sort as an alternative approach.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 7min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of graph reachability, ability to identify zero in-degree nodes as sources, and your skill in optimizing naive solutions.

Common Follow-ups

• What if the graph contains cycles? → The problem states DAG, but cycles would require cycle detection.
• Can you return the nodes in any order? → Yes, any order is acceptable.
• How to handle disconnected components? → Zero in-degree nodes in each component must be included.
• What if edges are duplicated? → Problem states edges are unique, but duplicates would require preprocessing.

💡 These follow-ups test your understanding of graph properties, edge cases, and problem constraints.

🔍

Pattern Recognition

When to Use

1) Problem involves directed graph, 2) Need minimal set of nodes to reach all others, 3) Graph is a DAG, 4) Zero in-degree nodes are mentioned or implied.

Signature Phrases

'minimum number of vertices to reach all nodes''directed acyclic graph''zero in-degree nodes''sources of the graph'

NOT This Pattern When

Problems involving undirected graphs, cycles, or shortest paths are different patterns.

Similar Problems

Find Eventual Safe States - also uses graph traversal and node classificationCourse Schedule - uses zero in-degree nodes and topological sortMinimum Number of Arrows to Burst Balloons - greedy but conceptually about minimal coverage

Practice

1. You are given a grid representing oranges where each cell can be empty, fresh, or rotten. Every minute, any fresh orange adjacent (up, down, left, right) to a rotten orange becomes rotten. Which algorithmic approach guarantees the minimum time to rot all fresh oranges or determine if impossible?

easy

A. Greedy approach that rots the freshest orange closest to any rotten orange each minute

B. Multi-source Breadth-First Search (BFS) starting from all rotten oranges simultaneously

C. Dynamic Programming to store minimum rot times for each cell independently

D. Depth-First Search (DFS) from a single rotten orange to propagate rot times

Solution

1. Step 1: Understand problem dynamics

   The rot spreads simultaneously from all rotten oranges each minute, so processing them in parallel is essential.

2. Step 2: Identify algorithm that models simultaneous spread

   Multi-source BFS naturally simulates spreading from multiple sources in waves, ensuring minimum time to rot all reachable fresh oranges.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Multi-source BFS models simultaneous spread correctly [OK]

Hint: Rot spreads simultaneously -> multi-source BFS needed [OK]

Common Mistakes:

• Using DFS from one source misses simultaneous spread
• Greedy picks local best but not global minimum
• DP doesn't fit simultaneous wave propagation

2. What is the time complexity of the optimal Kahn's Algorithm solution for the Course Schedule problem, given V courses and E prerequisite pairs?

medium

A. O(V + E) because each node and edge is processed once in BFS

B. O(V * E) due to nested loops over nodes and edges

C. O(V^2) because each node might be checked against all others

D. O(E) only, since edges dominate the processing time

Solution

1. Step 1: Identify operations on nodes and edges

   Each node is enqueued and dequeued once; each edge is visited once when decrementing in-degree.

2. Step 2: Combine to get total complexity

   Total time is proportional to number of nodes plus number of edges -> O(V + E).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Standard BFS topological sort runs in linear time relative to graph size [OK]

Hint: Each edge and node processed once -> O(V + E) [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing dense graph worst case with typical complexity
• Ignoring that BFS processes nodes once

3. What is the time complexity of the optimal approach using a single trust score array to find the town judge, given n people and m trust pairs?

medium

A. O(n * m) because we scan trust pairs for each person

B. O(n^2) because we check trust relationships pairwise

C. O(m^2) because trust pairs are nested in loops

D. O(n + m) because we process each trust pair once and then scan all people once

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates once over all trust pairs (m) and then once over all people (n).

2. Step 2: Combine complexities

   Processing trust pairs is O(m), scanning people is O(n), total O(n + m).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single pass over trust and people arrays [OK]

Hint: Single pass over trust pairs and people yields O(n + m) [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing trust pairs count with people count
• Ignoring linear scans after trust processing

4. What is the time complexity of the Bellman-Ford algorithm as implemented for the Network Delay Time problem with n nodes and E edges?

medium

A. O(E^2) -- quadratic in number of edges due to nested loops

B. O(n + E) -- linear in nodes and edges

C. O(n * E) -- relaxing all edges up to n-1 times

D. O(n^2) -- quadratic in number of nodes due to repeated relaxation

Solution

1. Step 1: Identify outer loop runs n-1 times and inner loop iterates over all E edges

   Each iteration relaxes edges once, so total operations are proportional to n * E

2. Step 2: Understand that E can be up to O(n^2) in dense graphs, but complexity is expressed as O(n * E)

   Options C and D confuse E and n; O(n + E) -- linear in nodes and edges underestimates complexity by ignoring repeated relaxation

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bellman-Ford complexity is O(n * E) [OK]

Hint: Bellman-Ford relaxes all edges n-1 times -> O(n * E) [OK]

Common Mistakes:

• Confusing E with n and saying O(n^2)
• Assuming linear time O(n + E)
• Thinking nested loops over edges cause O(E^2)

5. Suppose the Surrounded Regions problem is modified so that the board can be very large and the number of 'O's connected to the boundary is small. Which of the following modifications to the BFS approach would improve space efficiency without sacrificing correctness?

hard

A. Use DFS with recursion instead of BFS to avoid storing a large queue.

B. Only enqueue boundary 'O's and avoid marking visited cells, relying on board state changes.

C. Use BFS but mark visited cells in-place and prune early when no new 'O's are found.

D. Run BFS from every 'O' cell to ensure all regions are checked independently.

Solution

1. Step 1: Consider space usage of BFS queue

   BFS queue can grow large if many 'O's are connected; marking visited in-place helps avoid revisiting.

2. Step 2: Prune BFS early when no new 'O's are found

   This reduces unnecessary queue growth and improves space efficiency without losing correctness.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   In-place marking plus pruning optimizes BFS space [OK]

Hint: In-place marking and pruning reduce BFS queue size [OK]

Common Mistakes:

• Using DFS recursion can cause stack overflow on large boards.
• Not marking visited cells causes infinite loops or revisits.
• Running BFS from every 'O' is inefficient and unnecessary.