⚡Flashcard Drill➔
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

  1. Process values in increasing order and activate nodes as their value is reached.
  2. When a node becomes active, union it with its already-active neighbours.
  3. After activating all nodes of value v, count how many of them lie in the same component: each pair is a good path.
  4. 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 n handles 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems