#2421

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Good Paths

Count all good paths in a tree by scanning node values and using hash maps to track valid connections efficiently.

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.

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.

terminal

Solution

Solution 1: Sorting + Union Find

To ensure that the starting point (or endpoint) of the path is greater than or equal to all points on the path, we can consider sorting all points from small to large first, then traverse and add them to the connected component, specifically as follows:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class Solution:
    def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)

        n = len(vals)
        p = list(range(n))
        size = defaultdict(Counter)
        for i, v in enumerate(vals):
            size[i][v] = 1

        ans = n
        for v, a in sorted(zip(vals, range(n))):
            for b in g[a]:
                if vals[b] > v:
                    continue
                pa, pb = find(a), find(b)
                if pa != pb:
                    ans += size[pa][v] * size[pb][v]
                    p[pa] = pb
                    size[pb][v] += size[pa][v]
        return ans

Continue Practicing

#2368 reachable nodes with restrictions #1782 count pairs of nodes #1697 checking existence of edge length limited paths