Number of Good Paths
01 · Problem
You are given a tree with n nodes labelled 0 to n - 1. Node i has value vals[i], and edges[j] = [a_j, b_j] is an undirected edge between a_j and b_j.
A good path is a simple path in the tree where:
- both endpoints have the same value, and
- no node on the path has a value greater than that endpoint value.
Return the number of distinct good paths. A path and its reverse count as the same path, and every single node on its own is a good path.
02 · Examples
vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
6
The 5 single-node paths are good, plus the path 1 -> 0 -> 2 -> 4, whose endpoints both have value 3 and whose largest value is 3.
vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]
7
Besides the 5 single nodes, 0 -> 1 (both value 1, nothing larger in between) and 2 -> 3 (both value 2) are good.
vals = [1], edges = []
1
The lone node forms one good path by itself.
03 · Constraints
- 01n == vals.length
- 021 <= n <= 3 * 104
- 030 <= vals[i] <= 105
- 04edges.length == n - 1 and the edges form a valid tree.
- 050 <= a_j, b_j < n and a_j != b_j
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.