How do you solve Reachable Nodes With Restrictions on LeetCode?

Reachable Nodes With Restrictions (LeetCode #2368) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a set for restricted nodes allows for O(1) lookup time, making the traversal efficient.

What is the brute force solution for Reachable Nodes With Restrictions?

The brute force approach for Reachable Nodes With Restrictions is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves exploring all possible paths from node 0 to count reachable nodes, but it doesn't account for restricted nodes efficiently. We can use a depth-first search (DFS) to traverse the tree and check each node. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Reachable Nodes With Restrictions?

Always clarify the constraints and edge cases before diving into coding. Consider both BFS and DFS approaches and choose based on the problem's requirements. Explain your thought process clearly while coding, as it helps interviewers understand your reasoning.

What are common mistakes when solving Reachable Nodes With Restrictions?

Not using a set for restricted nodes, leading to inefficient checks. Failing to mark nodes as visited, causing infinite loops.

#2368

Reachable Nodes With Restrictions

Medium

ArrayHash TableTreeDepth-First SearchBreadth-First SearchUnion-FindGraph TheoryGraph Traversal (DFS/BFS)Set for fast membership checking

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a breadth-first search (BFS) or depth-first search (DFS) to traverse the tree while avoiding restricted nodes. This approach ensures we only visit each node once, making it efficient.

⚙️

Algorithm

3 steps

1Step 1: Construct an adjacency list from the edges to represent the tree.
2Step 2: Initialize a set for restricted nodes for O(1) lookup.
3Step 3: Use BFS or DFS starting from node 0, marking nodes as visited and counting reachable nodes while skipping restricted ones.

solution.py24 lines

1# Full working Python code
2from collections import defaultdict, deque
3
4def reachableNodes(n, edges, restricted):
5    graph = defaultdict(list)
6    for a, b in edges:
7        graph[a].append(b)
8        graph[b].append(a)
9    visited = set()
10    restricted_set = set(restricted)
11    count = 0
12    queue = deque([0])
13
14    while queue:
15        node = queue.popleft()
16        if node in visited or node in restricted_set:
17            continue
18        visited.add(node)
19        count += 1
20        for neighbor in graph[node]:
21            if neighbor not in visited:
22                queue.append(neighbor)
23
24    return count

ℹ

Complexity note: The optimal solution runs in O(n) time because each node and edge is processed exactly once. The space complexity is O(n) due to the storage of the graph and visited nodes.

1Using a set for restricted nodes allows for O(1) lookup time, making the traversal efficient.
2BFS or DFS ensures that we explore all reachable nodes without revisiting them.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.