Reachable Nodes With Restrictions
MedPrompt
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] = [ai, bi] indicates that there is an edge between nodes ai and bi 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 <= 105edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedgesrepresents a valid tree.1 <= restricted.length < n1 <= restricted[i] < n- All the values of
restrictedare unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves building a graph representation of the tree and then performing a standard graph traversal (like Breadth-First Search or Depth-First Search) starting from node 0. The key inefficiency in this method is how we check if a node is restricted. For every node we consider visiting, we perform a linear scan through the entire restricted array to see if it's present. While simple to implement, this repeated linear search leads to a high time complexity, making it unsuitable for large inputs.
Algorithm
- Build an adjacency list representation of the tree from the
edgesarray. - Initialize a queue for Breadth-First Search (BFS) and add node
0. - Initialize a
visitedboolean array of sizenand markvisited[0]as true. - Initialize a counter
reachableCountto 1. - While the queue is not empty:
- Dequeue a node
u. - For each neighbor
vofu:- If
vhas not been visited:- Linearly search for
vin therestrictedarray. - If
vis not found inrestricted:- Mark
vas visited. - Enqueue
v. - Increment
reachableCount.
- Mark
- Linearly search for
- If
- Dequeue a node
- Return
reachableCount.
Walkthrough
First, we construct an adjacency list from the input edges array. This allows us to easily find the neighbors of any given node. We then initialize a queue for BFS, a visited array to track visited nodes, and a counter for reachable nodes. We start by adding node 0 to the queue and marking it as visited.
We then enter a loop that continues as long as the queue is not empty. In each iteration, we dequeue a node. For each neighbor of the dequeued node, we first check if it has been visited. If not, we then check if it is a restricted node. This check is done by iterating through the restricted array. If the neighbor is not visited and not restricted, we mark it as visited, enqueue it, and increment our counter of reachable nodes. The process continues until the queue is empty, at which point the counter holds the total number of nodes reachable from node 0.
import java.util.*; class Solution { public int reachableNodes(int n, int[][] edges, int[] restricted) { // Step 1: Build adjacency list List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { adj.get(edge[0]).add(edge[1]); adj.get(edge[1]).add(edge[0]); } // Step 2: Initialize for BFS Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[n]; int count = 0; // Node 0 is not restricted, start from here queue.offer(0); visited[0] = true; count++; // Step 3: Perform BFS while (!queue.isEmpty()) { int u = queue.poll(); for (int v : adj.get(u)) { // Check if neighbor is visited if (!visited[v]) { // Step 4: Linearly scan restricted array boolean isRestricted = false; for (int r : restricted) { if (v == r) { isRestricted = true; break; } } if (!isRestricted) { visited[v] = true; queue.offer(v); count++; } } } } return count; }}Complexity
Time
O(N * R), where `N` is the number of nodes and `R` is the length of the `restricted` array. Building the adjacency list takes `O(N)`. The BFS traversal visits each node at most once. For each node, we iterate its neighbors. The total number of edges considered is `2 * (N-1)`. For each potential new node to visit, we perform a linear scan of the `restricted` array, which takes `O(R)`. This results in a total time complexity dominated by `O(N * R)`.
Space
O(N). We need O(N) space for the adjacency list, O(N) for the `visited` array, and O(N) for the queue in the worst case (a star graph or line graph). This sums to O(N).
Trade-offs
Pros
Conceptually simple, directly translating the problem statement.
Doesn't require complex data structures beyond a list and a queue.
Cons
Very inefficient due to the repeated linear scan of the
restrictedarray.Will result in a "Time Limit Exceeded" (TLE) error for the given constraints.
This approach significantly improves upon the previous one by optimizing the check for restricted nodes. Instead of a linear scan, we first store all restricted nodes in a HashSet. This allows for an average time complexity of O(1) for checking if a node is restricted. We then perform a Depth-First Search (DFS) starting from node 0. The recursive nature of DFS naturally explores the graph, and at each step, we use the hash set to quickly decide if we can proceed to a neighbor.
Algorithm
- Create a
HashSetfrom therestrictedarray for O(1) average time lookups. - Build an adjacency list for the tree.
- Initialize a
visitedboolean array of sizen. - Define a recursive DFS function
dfs(node):- If
nodeis in the restricted set, return 0. - Mark
nodeas visited. - Initialize
count = 1(for the current node). - For each neighbor
vofnode:- If
vis not visited:- Add the result of
dfs(v)tocount.
- Add the result of
- If
- Return
count.
- If
- Call
dfs(0)to start the traversal and get the result.
Walkthrough
The first step is to process the restricted array into a HashSet for efficient lookups. This takes time proportional to the number of restricted nodes. Next, we build the adjacency list representation of the tree, just as in the previous approach. We also need a visited array to prevent re-visiting nodes.
We then initiate a recursive DFS function, starting with dfs(0). This function will return the count of reachable nodes in the component connected to the current node.
The dfs function works as follows:
- First, it checks if the current node is restricted. If so, it cannot be part of the reachable set, so we return 0.
- Mark the current node as visited.
- Initialize a local count to 1 (for the current node itself).
- Iterate through all neighbors of the current node.
- For each neighbor, if it has not been visited, recursively call
dfson that neighbor and add the returned count to the local count. - Return the total local count.
The initial call to dfs(0) will give the final answer.
import java.util.*; class Solution { private List<List<Integer>> adj; private Set<Integer> restrictedSet; private boolean[] visited; public int reachableNodes(int n, int[][] edges, int[] restricted) { // Step 1: Build adjacency list adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { adj.get(edge[0]).add(edge[1]); adj.get(edge[1]).add(edge[0]); } // Step 2: Store restricted nodes in a HashSet for O(1) lookups restrictedSet = new HashSet<>(); for (int node : restricted) { restrictedSet.add(node); } // Step 3: Initialize visited array and start DFS visited = new boolean[n]; return dfs(0); } private int dfs(int u) { // A node is not reachable if it's restricted if (restrictedSet.contains(u)) { return 0; } visited[u] = true; int count = 1; // Count the current node for (int v : adj.get(u)) { if (!visited[v]) { count += dfs(v); } } return count; }}Complexity
Time
O(N + R), where `N` is the number of nodes and `R` is the number of restricted nodes. Building the adjacency list takes `O(N)`. Populating the hash set takes `O(R)`. The DFS traversal visits each reachable node and edge once, which takes `O(N)` time in the worst case. Thus, the total time complexity is `O(N + R)`.
Space
O(N + R). `O(N)` for the adjacency list, `O(N)` for the `visited` array, `O(R)` for the restricted set, and `O(N)` for the recursion stack in the worst case (a skewed tree). This simplifies to `O(N + R)`.
Trade-offs
Pros
Highly efficient and optimal for the given constraints.
The use of a hash set for restricted nodes is a key optimization.
Cons
The recursive implementation might lead to a
StackOverflowErrorfor very deep trees, which is a possibility with N up to 10^5.
This approach is an iterative alternative to the recursive DFS, using Breadth-First Search (BFS). It shares the same core optimization of using a HashSet for O(1) checks of restricted nodes. BFS explores the graph level by level, which can be advantageous in some scenarios, such as finding the shortest path. For this problem, its performance is equivalent to DFS. It uses a queue to manage the nodes to visit, avoiding deep recursion and the potential for stack overflow errors.
Algorithm
- Create a
HashSetfrom therestrictedarray. - Build an adjacency list for the tree.
- Initialize a queue and add node
0. - Initialize a
visitedboolean array and markvisited[0]as true. - Initialize
reachableCount = 1. - While the queue is not empty:
- Dequeue a node
u. - For each neighbor
vofu:- If
vis not visited and not in the restricted set:- Mark
vas visited. - Enqueue
v. - Increment
reachableCount.
- Mark
- If
- Dequeue a node
- Return
reachableCount.
Walkthrough
Similar to the DFS approach, we begin by building the adjacency list and populating a HashSet with the restricted nodes. We then initialize a queue and add the starting node, 0. We also use a visited array to keep track of nodes already added to the queue to avoid redundant processing. We initialize a counter for reachable nodes to 1, since we start at node 0.
The main part of the algorithm is a loop that runs as long as the queue is not empty. Inside the loop:
- We dequeue a node
u. - We iterate through all its neighbors
v. - For each neighbor
v, we check if it has been visited and if it is in therestrictedSet. - If
vis unvisited and not restricted, we mark it as visited, increment our reachable node counter, and enqueuevfor future processing.
After the loop terminates (meaning we have explored all reachable, non-restricted nodes), the counter will hold the final answer.
import java.util.*; class Solution { public int reachableNodes(int n, int[][] edges, int[] restricted) { // Step 1: Build adjacency list List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } for (int[] edge : edges) { adj.get(edge[0]).add(edge[1]); adj.get(edge[1]).add(edge[0]); } // Step 2: Store restricted nodes in a HashSet for O(1) lookups Set<Integer> restrictedSet = new HashSet<>(); for (int node : restricted) { restrictedSet.add(node); } // Step 3: Initialize for BFS Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[n]; int count = 0; // Start from node 0, which is guaranteed not to be restricted queue.offer(0); visited[0] = true; count = 1; // Step 4: Perform BFS while (!queue.isEmpty()) { int u = queue.poll(); for (int v : adj.get(u)) { if (!visited[v] && !restrictedSet.contains(v)) { visited[v] = true; count++; queue.offer(v); } } } return count; }}Complexity
Time
O(N + R). `O(N)` for building the adjacency list, `O(R)` for the hash set, and `O(N)` for the BFS traversal. Each reachable node and edge is processed once.
Space
O(N + R). `O(N)` for the adjacency list, `O(N)` for the `visited` array, `O(R)` for the restricted set, and `O(N)` for the queue in the worst case.
Trade-offs
Pros
Optimal time and space complexity.
Iterative approach avoids potential
StackOverflowErrorthat can occur with deep recursion in DFS.Generally considered safer for very large graphs compared to recursive DFS.
Cons
The code can be slightly more verbose than a recursive DFS implementation.
Solutions
Solution
class Solution {private List<Integer>[] g;private boolean[] vis;private int ans;public int reachableNodes(int n, int[][] edges, int[] restricted) { g = new List[n]; Arrays.setAll(g, k->new ArrayList<>()); vis = new boolean[n]; for (int v : restricted) { vis[v] = true; } for (int[] e : edges) { int a = e[0], b = e[1]; g[a].add(b); g[b].add(a); } ans = 0; dfs(0); return ans; }private void dfs(int u) { if (vis[u]) { return; } ++ans; vis[u] = true; for (int v : g[u]) { dfs(v); } }}class Solution {public: int ans; int reachableNodes(int n, vector<vector<int>> &edges, vector<int> &restricted) { vector<vector<int>> g(n); for (auto &e : edges) { int a = e[0], b = e[1]; g[a].push_back(b); g[b].push_back(a); } vector<bool> vis(n); for (int v : restricted) vis[v] = true; ans = 0; dfs(0, g, vis); return ans; } void dfs(int u, vector<vector<int>> &g, vector<bool> &vis) { if (vis[u]) return; vis[u] = true; ++ans; for (int v : g[u]) dfs(v, g, vis); }};class Solution: def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int: g = defaultdict(list) vis = [False] * n for v in restricted: vis[v] = True for a, b in edges: g[a]. append(b) g[b]. append(a) def dfs(u): nonlocal ans if vis[u]: return ans += 1 vis[u] = True for v in g[u]: dfs(v) ans = 0 dfs(0) return ansVideo 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.