MediumNo. 2368

Reachable Nodes With Restrictions — LeetCode 2368 Python Solution

Pattern
Union-Find
Topics
Tree, Depth-First Search, Breadth-First Search, Union Find, Graph, Array, Hash Table
Reading time
3 min

The problem

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.

Example

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.

Python solution

PythonSolution
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)

Complexity

Time
O(n)
Space · auxiliary
O(n)

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2368. Reachable Nodes With Restrictions is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0924Minimize Malware SpreadHard
0928Minimize Malware Spread IIHard
0690Employee ImportanceMedium
0721Accounts MergeMedium
0839Similar String GroupsHard
0959Regions Cut By SlashesMedium

Frequently asked questions

How hard is LeetCode 2368. Reachable Nodes With Restrictions?

LeetCode 2368. Reachable Nodes With Restrictions is rated Medium on LeetCode.

What is the time complexity of LeetCode 2368. Reachable Nodes With Restrictions?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2368. Reachable Nodes With Restrictions?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 2368. Reachable Nodes With Restrictions cover?

LeetCode 2368. Reachable Nodes With Restrictions is tagged Tree, Depth-First Search, Breadth-First Search, Union Find, Graph, Array and Hash Table on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.