Watch 10 video solutions for Number of Good Paths, a hard level problem involving Array, Hash Table, Tree. This walkthrough by NeetCodeIO has 18,304 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
You are given a 0-indexed integer array vals of length n where vals[i] denotes the value of the ith node. You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
A good path is a simple path that satisfies the following conditions:
Return the number of distinct good paths.
Note that a path and its reverse are counted as the same path. For example, 0 -> 1 is considered to be the same as 1 -> 0. A single node is also considered as a valid path.
Example 1:
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. There is 1 additional good path: 1 -> 0 -> 2 -> 4. (The reverse path 4 -> 2 -> 0 -> 1 is treated as the same as 1 -> 0 -> 2 -> 4.) Note that 0 -> 2 -> 3 is not a good path because vals[2] > vals[0].
Example 2:
Input: vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]] Output: 7 Explanation: There are 5 good paths consisting of a single node. There are 2 additional good paths: 0 -> 1 and 2 -> 3.
Example 3:
Input: vals = [1], edges = [] Output: 1 Explanation: The tree consists of only one node, so there is one good path.
Constraints:
n == vals.length1 <= n <= 3 * 1040 <= vals[i] <= 105edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedges represents a valid tree.Problem Overview: You are given a tree where each node has a value. A path is considered good if the maximum value along the path is equal to the values of both endpoints. The task is to count all such valid paths, including single-node paths.
Approach 1: DFS with Path Tracking (O(n^2) time, O(n) space)
This approach treats every node as a potential starting point and explores reachable nodes using depth‑first search. While traversing, maintain the maximum value encountered along the current path and check whether the endpoint satisfies the good path condition. Because the graph is a tree, each DFS explores unique paths without cycles, but repeating the search from every node leads to many redundant traversals. A small optimization is pruning branches when a node value exceeds the starting node’s value since that path can never form a valid good path. Despite pruning, the worst case still reaches O(n^2) time when many nodes share similar values.
This method helps you reason about the definition of a good path and understand the constraints of the problem, but it does not scale well for large inputs.
Approach 2: Union-Find with Value Grouping (O(n log n) time, O(n) space)
The optimal strategy processes nodes in increasing order of their values. First sort nodes by value. Then gradually connect nodes using a Union-Find structure while only merging neighbors whose values are less than or equal to the current node value. This ensures that when two nodes are connected, all nodes in that component have values not exceeding the current threshold.
For each value group, count how many nodes with that value exist inside each connected component. If a component contains k nodes with the same value, it contributes k * (k - 1) / 2 additional good paths because every pair can form a valid path whose maximum equals that value. Union-Find operations such as find and union run in near constant time with path compression. Sorting the nodes dominates the runtime, giving overall complexity O(n log n).
This technique combines graph connectivity with sorting. The key insight is that processing values in ascending order guarantees that newly formed components never introduce invalid higher values on the path.
Recommended for interviews: The Union-Find approach is what most interviewers expect. The DFS approach shows you understand the definition of a valid path, but recognizing that the problem can be converted into incremental connectivity with Union-Find demonstrates stronger algorithmic insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Path Tracking | O(n^2) | O(n) | Useful for understanding the definition of good paths or when constraints are small. |
| Union-Find with Value Grouping | O(n log n) | O(n) | Best general solution for large inputs. Efficiently tracks connected components while processing node values in sorted order. |