#2368

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Reachable Nodes With Restrictions

In the 'Reachable Nodes With Restrictions' problem, find the maximum reachable nodes from node 0 in a tree while avoiding restricted nodes.

array hash table tree depth first search breadth first search

Problem Statement

You are given an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. A 2D array edges represents the tree structure, where each entry edges[i] = [ai, bi] indicates an edge between nodes ai and bi. In addition, you're provided with a list of restricted nodes that cannot be visited during traversal.

Your goal is to determine the maximum number of nodes that can be reached from node 0, ensuring that none of the restricted nodes are visited. The tree guarantees that there is exactly one path between any two nodes.

Examples

Example 1

Input: n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]

Output: 4

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

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 <= 105
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges represents a valid tree.
1 <= restricted.length < n
1 <= restricted[i] < n
All the values of restricted are unique.

Solution Approach

Tree Traversal with DFS or BFS

Perform a Depth-First Search (DFS) or Breadth-First Search (BFS) starting from node 0. During the traversal, avoid visiting restricted nodes. Maintain a visited set to ensure nodes aren't revisited.

Array Scanning and Hash Lookup

Leverage array scanning to go through the edges and build the tree representation. Use a hash set to quickly check if a node is restricted during traversal, allowing for efficient skipping of invalid nodes.

Optimizing with Early Stopping

In some cases, if all reachable nodes have been visited before the entire tree is traversed, the search can be terminated early. This avoids unnecessary work and improves efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexities depend on the final approach chosen. DFS or BFS typically run in O(n) time, where n is the number of nodes. The space complexity is also O(n) due to the need to store the visited set and tree structure.

What Interviewers Usually Probe

Candidate shows an understanding of tree traversal techniques like DFS or BFS.
Candidate is able to use hash sets for efficient lookups, avoiding restricted nodes.
Candidate demonstrates optimization skills by considering early termination in traversal.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly handle the restricted nodes, causing the traversal to incorrectly include invalid nodes.
Incorrectly managing the visited set, leading to cycles or revisiting nodes.
Not optimizing the traversal, leading to unnecessary checks or excessive computation.

Follow-up variants

What if there are additional restrictions such as time limits on traversal?
Can this problem be solved with a Union-Find approach instead of DFS or BFS?
How would the solution change if there were multiple starting nodes?

FAQ

What is the time complexity of the Reachable Nodes With Restrictions problem?

The time complexity is typically O(n) where n is the number of nodes in the tree, due to the single traversal of the tree.

What pattern is used to solve the Reachable Nodes With Restrictions problem?

The solution relies on array scanning combined with hash lookup for efficient node checking and traversal.

How do you handle restricted nodes during the traversal?

By maintaining a hash set of restricted nodes, you can efficiently check during traversal whether a node is restricted and skip it if necessary.

Can the solution be optimized further?

Yes, early stopping can be implemented to terminate the traversal once all reachable nodes have been visited, improving efficiency.

Is BFS or DFS better for this problem?

Both BFS and DFS are valid approaches, but the choice depends on the specific problem constraints and preference for iterative versus recursive solutions.

terminal

Solution

Solution 1: DFS

First, we construct an adjacency list $g$ based on the given edges, where $g[i]$ represents the list of nodes adjacent to node $i$. Then we define a hash table $vis$ to record the restricted nodes or nodes that have been visited, and initially add the restricted nodes to $vis$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def reachableNodes(
        self, n: int, edges: List[List[int]], restricted: List[int]
    ) -> int:
        def dfs(i: int) -> int:
            vis.add(i)
            return 1 + sum(j not in vis and dfs(j) for j in g[i])

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = set(restricted)
        return dfs(0)

Solution 2: BFS

Similar to Solution 1, we first construct an adjacency list $g$ based on the given edges, then define a hash table $vis$ to record the restricted nodes or nodes that have been visited, and initially add the restricted nodes to $vis$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def reachableNodes(
        self, n: int, edges: List[List[int]], restricted: List[int]
    ) -> int:
        def dfs(i: int) -> int:
            vis.add(i)
            return 1 + sum(j not in vis and dfs(j) for j in g[i])

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = set(restricted)
        return dfs(0)

Continue Practicing

#2421 number of good paths #2467 most profitable path in a tree #3493 properties graph