To solve Number of Good Paths, process nodes from smallest to largest value and use union-find to track connected components. Maintain hash maps to count nodes with identical values within each component. Sum these counts carefully to capture all good paths while avoiding overcounting overlapping segments.
Problem Statement
You are given a tree with n nodes labeled from 0 to n - 1 and exactly n - 1 edges forming an undirected acyclic graph. Each node i has a value vals[i].
A good path is defined as a simple path where the maximum value along the path is equal to the value of both endpoints. Compute the total number of good paths in the tree.
Examples
Example 1
Input: vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
Output: 6
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
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
The tree consists of only one node, so there is one good path.
Constraints
- n == vals.length
- 1 <= n <= 3 * 104
- 0 <= vals[i] <= 105
- edges.length == n - 1
- edges[i].length == 2
- 0 <= ai, bi < n
- ai != bi
- edges represents a valid tree.
Solution Approach
Sort Nodes by Value
Process nodes in ascending order of vals[i] so that union operations only combine components with nodes of smaller or equal values. This ensures correct counting of good paths as larger nodes do not violate the path maximum rule.
Union-Find Component Tracking
Use a union-find structure to merge connected nodes as you scan. Maintain counts of nodes with identical values in each component. When merging, multiply counts of identical values to calculate new good paths contributed by the merge.
Hash Map Counting
Within each connected component, store counts of node values in a hash map. This allows O(1) access to the number of nodes with a specific value, enabling efficient computation of additional good paths without revisiting nodes repeatedly.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n log n + n α(n)) due to sorting nodes and performing near-constant-time union-find operations. Space complexity is O(n) for union-find arrays and hash maps used to count nodes per component.
What Interviewers Usually Probe
- Ask if the candidate can process nodes in order of increasing value.
- Check whether the candidate tracks counts per connected component to avoid double-counting.
- Probe if the candidate correctly handles single-node paths as part of the total.
Common Pitfalls or Variants
Common pitfalls
- Merging components without considering value order, which leads to invalid good paths.
- Forgetting to count single-node paths as valid good paths.
- Overcounting paths by not tracking identical-value nodes separately within components.
Follow-up variants
- Count good paths where the minimum value along the path equals the endpoint values instead of the maximum.
- Allow weighted edges and count good paths where the maximum node value does not exceed a threshold.
- Compute good paths in a forest rather than a single tree.
How GhostInterview Helps
- Automatically organizes nodes by value and tracks components to ensure all valid paths are counted efficiently.
- Highlights potential overcounting errors and provides step-by-step union-find merging guidance.
- Generates explanations for why certain paths are invalid due to the maximum-value constraint, saving debugging time.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What defines a good path in the Number of Good Paths problem?
A good path is any simple path where the maximum value along the path equals the values of both endpoints.
Can single-node paths be considered good paths?
Yes, every individual node forms a good path by itself and must be included in the total count.
How does sorting nodes by value help?
Processing nodes from smallest to largest ensures that union operations never connect higher-value nodes prematurely, maintaining path validity.
Why use a hash map for counting within components?
It allows O(1) access to the number of nodes with identical values, enabling efficient calculation of new good paths when components merge.
What is the main pattern for solving this problem efficiently?
The core pattern is array scanning plus hash lookup combined with union-find to count connected nodes with equal values without overcounting.
Need direct help with Number of Good Paths instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Number of Good Paths from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
In the 'Reachable Nodes With Restrictions' problem, find the maximum reachable nodes from node 0 in a tree while avoiding restricted nodes.
Open problem page#1782 Count Pairs Of NodesGiven a graph with nodes and edges, count pairs of nodes where the degree sum exceeds a given threshold for each query.
Open problem page#1697 Checking Existence of Edge Length Limited PathsSolve the problem of checking if there exists a path between two nodes under edge length constraints using efficient techniques like two-pointer scanning and union-find.
Open problem page