Is Reachable Nodes With Restrictions easy or hard?

Reachable Nodes With Restrictions is generally classified as a Medium problem. The logic relies on standard DFS or BFS traversal, but the restricted node constraint requires careful filtering during traversal and correct graph construction.

How to solve Reachable Nodes With Restrictions in O(n)?

Construct an adjacency list from the edge list and store restricted nodes in a hash set. Start DFS or BFS from node 0, and only visit neighbors that are not restricted and not already visited. Because the graph is a tree with n−1 edges, the traversal processes each node once, achieving O(n) time.

What is the best approach for Reachable Nodes With Restrictions?

The best approach is graph traversal using either DFS or BFS with an adjacency list. Store restricted nodes in a hash set for O(1) checks and traverse from node 0 while skipping restricted nodes. Since the graph is a tree, each node is visited at most once, giving an O(n) time solution.

Is Reachable Nodes With Restrictions asked at Google/Amazon/Meta?

Graph traversal problems with constraints frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving restricted nodes, blocked vertices, or reachability in trees are common because they test DFS/BFS fundamentals and graph modeling skills.

What data structure is used in Reachable Nodes With Restrictions?

The solution typically uses an adjacency list to represent the graph, a hash set to store restricted nodes for constant-time lookups, and either a recursion stack (DFS) or queue (BFS) for traversal. A visited set or boolean array prevents revisiting nodes.

What is the time complexity of Reachable Nodes With Restrictions?

The optimal solution runs in O(n) time where n is the number of nodes. Building the adjacency list takes O(n), and the DFS or BFS traversal also visits each node once. Space complexity is O(n) due to the adjacency list, visited tracking, and recursion stack or queue.

Reachable Nodes With Restrictions Python or Java solution approach?

Both Python and Java implementations follow the same structure: build an adjacency list, place restricted nodes in a set, and run DFS or BFS from node 0. Python often uses recursion or collections.deque for BFS, while Java uses ArrayList for adjacency lists and a Queue for traversal.

Description Hints 3 Solution Video 8:27

2368. Reachable Nodes With Restrictions

Medium60.8% acceptance2 companies

There is an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.

You are given a 2D integer array edges of length n - 1 where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the tree. You are also given an integer array restricted which represents restricted nodes.

Return the maximum number of nodes you can reach from node 0 without visiting a restricted node.

Note that node 0 will not be a restricted node.

Example 1:

Input: n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
Output: 4
Explanation: The diagram above shows the tree.
We have that [0,1,2,3] are the only nodes that can be reached from node 0 without visiting a restricted node.

Example 2:

Input: n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
Output: 3
Explanation: The diagram above shows the tree.
We have that [0,5,6] are the only nodes that can be reached from node 0 without visiting a restricted node.

Constraints:

2 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
edges represents a valid tree.
1 <= restricted.length < n
1 <= restricted[i] < n
All the values of restricted are unique.

Asked at 2 companies

MakeMyTrip

Google

Topics

Hints open one at a time

Hint 1

Can we find all the reachable nodes in a single traversal?

Hint 2

Traverse the graph from node 0 while avoiding the nodes in restricted and do not revisit nodes that have been visited.

Hint 3

Keep count of how many nodes are visited in total.

8:27

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution