Reachable Nodes With Restrictions — Problem & Solution
Reachable Nodes With Restrictions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Reachable Nodes With Restrictions is a medium coding problem on arrays, depth-first search and breadth-first search, asked in Amazon, Google and Accenture interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Breadth-First Search, Trees, Graph, Union Find
- Asked at: Amazon, Google, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An undirected tree has n nodes labelled 0 … n - 1 and n - 1 edges. Some nodes are listed in restricted and may not be visited.
Return how many nodes can be reached from node 0, counting node 0 itself. Node 0 is never restricted.
Example 1
Input: n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
Output: 4
Explanation: Nodes 0, 1, 2 and 3; the branches through 4 and 5 are cut off.
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: Only nodes 0, 5 and 6 remain reachable.
Example 3
Input: n = 2, edges = [[0,1]], restricted = [1]
Output: 1
Constraints
2 <= n <= 10^5edges.length == n - 1edges[i].length == 20 <= edges[i][0], edges[i][1] < nedges represents a valid tree1 <= restricted.length < n1 <= restricted[i] < nAll the values of restricted are unique.
Hints for Reachable Nodes With Restrictions
Hint 1
Mark the restricted nodes in a boolean array first.
Hint 2
Then it is an ordinary traversal from node 0 that simply refuses to step onto a marked node.
Hint 3
Removing a restricted node from a tree disconnects everything behind it.
How to solve Reachable Nodes With Restrictions
Mark the restricted nodes, then run a depth-first or breadth-first search from node 0 that skips them, and count what it visits.
Approach
- Fill a
blockedarray fromrestricted. - Build the adjacency list from the edges, both directions.
- Traverse from node 0, never entering a blocked node.
- Return the number of nodes visited.
Why it works
In a tree there is exactly one path between any two nodes, so a restricted node on that path makes the far end unreachable — the traversal needs no special handling for cut branches, it simply never walks into one. An iterative stack is used rather than recursion because n reaches 100 000 and a path-shaped tree would blow the call stack.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- A
restrictedlist searched linearly per step isO(n · restricted); mark it in an array instead. - Edges are undirected, so both directions go into the adjacency list.
- Node 0 counts towards the answer.
Reference solution
Python
from typing import List
def reachableNodes(n: int, edges: List[List[int]], restricted: List[int]) -> int:
blocked = [False] * n
for r in restricted:
blocked[r] = True
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
if blocked[0]:
return 0
seen = [False] * n
seen[0] = True
stack = [0]
total = 0
while stack:
u = stack.pop()
total += 1
for v in adj[u]:
if seen[v] or blocked[v]:
continue
seen[v] = True
stack.append(v)
return totalJava
public static int reachableNodes(int n, int[][] edges, int[] restricted) {
boolean[] blocked = new boolean[n];
for (int r : restricted) blocked[r] = true;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
if (blocked[0]) return 0;
boolean[] seen = new boolean[n];
seen[0] = true;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
int total = 0;
while (!stack.isEmpty()) {
int u = stack.pop();
total++;
for (int v : adj.get(u)) {
if (seen[v] || blocked[v]) continue;
seen[v] = true;
stack.push(v);
}
}
return total;
}C++
int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
vector<char> blocked(n, 0);
for (int r : restricted) blocked[r] = 1;
vector<vector<int>> adj(n);
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
if (blocked[0]) return 0;
vector<char> seen(n, 0);
seen[0] = 1;
vector<int> stack = { 0 };
int total = 0;
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
total++;
for (int v : adj[u]) {
if (seen[v] || blocked[v]) continue;
seen[v] = 1;
stack.push_back(v);
}
}
return total;
}JavaScript
var reachableNodes = function(n, edges, restricted) {
var i;
var blocked = [], adj = [];
for (i = 0; i < n; i++) { blocked.push(false); adj.push([]); }
for (i = 0; i < restricted.length; i++) blocked[restricted[i]] = true;
for (i = 0; i < edges.length; i++) {
adj[edges[i][0]].push(edges[i][1]);
adj[edges[i][1]].push(edges[i][0]);
}
if (blocked[0]) return 0;
var seen = [];
for (i = 0; i < n; i++) seen.push(false);
seen[0] = true;
var stack = [0];
var total = 0;
while (stack.length > 0) {
var u = stack.pop();
total++;
for (i = 0; i < adj[u].length; i++) {
var v = adj[u][i];
if (seen[v] || blocked[v]) continue;
seen[v] = true;
stack.push(v);
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)