NeetCode #646LC-2421HardAdvanced Graphs
← Back to All Problems#646 · #2421 · Number of Good Paths(好路径的数目)
📌 Problem Statement & Constraints
You are given a tree of
n nodes with vals[i] and edges. A good path is a simple path whose two endpoints have the same value and every node on it has a value at most that value. Return the number of good paths. Constraints: 1 <= n <= 3 * 10^4, 1 <= vals[i] <= 10^5.💡 Core Algorithmic Approaches
- Process values in increasing order and activate nodes as their value is reached.
- When a node becomes active, union it with its already-active neighbours.
- After activating all nodes of value
v, count how many of them lie in the same component: each pair is a good path. - Single-node paths are counted by initialising the answer to
n.
💻 Benchmark Python3 Implementation
class Solution:
def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
from collections import defaultdict
n = len(vals)
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
by_val = defaultdict(list)
for i, v in enumerate(vals):
by_val[v].append(i)
active = [False] * n
res = n # every single node is a good path
for v in sorted(by_val):
# activate all nodes with this value and union with active neighbours
for i in by_val[v]:
active[i] = True
for j in g[i]:
if active[j]:
ri, rj = find(i), find(j)
if ri != rj:
parent[ri] = rj
# count pairs of this value that ended up in the same component
cnt = defaultdict(int)
for i in by_val[v]:
cnt[find(i)] += 1
for c in cnt.values():
res += c * (c - 1) // 2
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O((n + E) * alpha + n log n): the value sort dominates.
💾 Space Complexity
O(n + E) for the graph and the union-find.
⚠️ Interview Pitfalls & Follow-ups
- Processing nodes in arbitrary order: the activation order must follow increasing values.
- Counting pairs before all same-value nodes are activated: the component may still grow.
- Forgetting the single-node paths: initialising the answer to
nhandles them. - Unioning before activating the current node: the node itself must be active first.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.