Quarantine Reach
MediumGraphs
Problem
A city's n districts, numbered 0 to n - 1, are linked by n - 1 two-way roads given in edges, forming a tree. A health inspector starts in district 0.
The districts listed in restricted are under quarantine: the inspector may not enter them. Return how many districts (including district 0) the inspector can visit.
Example 1
- Input:
- n = 7, edges = [[0,1],[1,2],[1,3],[0,4],[4,5],[5,6]], restricted = [4,2]
- Output:
- 3
The inspector can reach 0, 1 and 3. District 4 blocks the way to 5 and 6, and district 2 is itself closed.
Example 2
- Input:
- n = 4, edges = [[0,1],[1,2],[2,3]], restricted = []
- Output:
- 4
Constraints
- 1 ≤ n ≤ 10^5
- edges.length = n - 1 and they form a tree
- 0 ≤ restricted.length < n
- District 0 is never restricted; restricted values are distinct.
Hint
Show the first hint
Restricted districts behave like nodes that were deleted from the graph.
Walkthrough
How to approach it
01Clarify before coding
- Is district 0 ever restricted? No.
- Can the inspector pass through a restricted district without stopping? No, entering is forbidden, so it blocks the path.
- Is the graph always a tree? Yes, so there is exactly one path between any two districts.
02Brute force
For every district, find the unique tree path from 0 and check whether it contains a restricted district.
Cost: Each path costs O(n), so O(n²) overall: 10^10 at n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.