Number of Good Paths

Number of Good Paths

What is this problem about?

The Number of Good Paths problem gives you a tree with node values. A "good path" is a path between two nodes (inclusive) where the maximum value on the path equals the values of both endpoints. Count all good paths (including single-node paths). This hard coding problem uses Union-Find with sorted node value processing.

Why is this asked in interviews?

Amazon, TikTok, and Google ask this hard graph/tree problem because it requires the insight that good paths always connect nodes with equal values where no intermediate node has a larger value. Processing nodes in order of value and using Union-Find to track connected components of equal-or-lower nodes enables efficient counting. The array, union find, hash table, graph, sorting, and tree interview pattern is comprehensively tested.

Algorithmic pattern used

Sort nodes by value + Union-Find. Sort all nodes by their value. Process nodes in increasing value order. For each group of nodes with the same value: connect each node to its already-processed (smaller-or-equal value) neighbors using Union-Find. After uniting, for each connected component containing these same-value nodes, if there are k such nodes in the component, add k*(k-1)/2 + k good paths (pairs between them + each with itself). Count carefully using component tracking.

Example explanation

Tree: nodes 0-4 with values [1,3,2,1,3]. Good paths: single-node paths (5), plus paths (0,3) (both value 1, max is max of path=3... wait need to check no larger node on path). Actually: good paths exist where both endpoints have the same value and no intermediate node exceeds that value. After sorting and Union-Find processing, count same-value nodes in the same component at each step.

Common mistakes candidates make

• Processing nodes in arbitrary order (must process smaller values first).
• Counting ordered pairs instead of unordered pairs (good paths are unordered).
• Not tracking which nodes in a Union-Find component have the current maximum value.
• Off-by-one: single-node paths should be counted (each node forms a good path with itself).

Interview preparation tip

Good Paths is a hard problem that requires combining three concepts: sorting for order of processing, Union-Find for connectivity, and counting pairs within components. The key insight: process nodes by value — when connecting a node to its neighbors, only connect if the neighbor has value ≤ current node's value. At each value level, count pairs of same-value nodes in the same component. Practice Union-Find with ordered processing on similar "count valid subtree paths" problems.