Number of Good Paths — LeetCode 2421 Python Solution
HardTreeUnion FindGraphArrayHash TableSorting
- Problem
- #2421
- Pattern
- Union-Find
- Reading time
- 5 min
- Source
- leetcode.com
The problem
There is a tree (i.e. a connected, undirected graph with no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges.
Example
- Input
- vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
- Output
- 6
- Explanation
- There are 5 good paths consisting of a single node.
Python solution
Python
class Solution:
def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
n = len(vals)
p = list(range(n))
size = defaultdict(Counter)
for i, v in enumerate(vals):
size[i][v] = 1
ans = n
for v, a in sorted(zip(vals, range(n))):
for b in g[a]:
if vals[b] > v:
continue
pa, pb = find(a), find(b)
if pa != pb:
ans += size[pa][v] * size[pb][v]
p[pa] = pb
size[pb][v] += size[pa][v]
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n) |
| Space | O(n) auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2421. Number of Good Paths 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
Frequently asked questions
- How hard is LeetCode 2421. Number of Good Paths?
- LeetCode 2421. Number of Good Paths is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2421. Number of Good Paths?
- The Python solution on this page runs in O(n \times \log n).
- What is the space complexity of LeetCode 2421. Number of Good Paths?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2421. Number of Good Paths cover?
- LeetCode 2421. Number of Good Paths is tagged Tree, Union Find, Graph, Array, Hash Table and Sorting on LeetCode.