Number of Good Paths Problem

Problem

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:

  1. The starting node and the ending node have the same value.
  2. All nodes between the starting node and the ending node have values less than or equal to the starting node (i.e. the starting node’s value should be the maximum value along the path).

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.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6

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:

1
2
3
4
5

Input:
vals = [1], edges = []
Output:
 1
Explanation: The tree consists of only one node, so there is one good path.

Solution

Method 1 – Union-Find with Value Grouping (1)

Intuition

The key idea is to process nodes in order of increasing value, using union-find to group nodes whose values are less than or equal to the current value. For each group, count the number of nodes with the current value and add the number of good paths contributed by this group.

Approach

  1. Build the graph as an adjacency list.
  2. For each unique value (in sorted order), process all nodes with that value:
    • For each neighbor with value <= current value, union the nodes.
  3. For each group (connected component), count the number of nodes with the current value and add count * (count + 1) // 2 to the answer.
  4. Return the total number of good paths.

Code

 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

class Solution {
public:
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int n = vals.size();
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        map<int, vector<int>> val2nodes;
        for (int i = 0; i < n; ++i) val2nodes[vals[i]].push_back(i);
        vector<int> par(n);
        iota(par.begin(), par.end(), 0);
        function<int(int)> find = [&](int x) { return par[x] == x ? x : par[x] = find(par[x]); };
        int ans = 0;
        for (auto& [v, nodes] : val2nodes) {
            for (int u : nodes) {
                for (int nei : g[u]) {
                    if (vals[nei] <= v) par[find(u)] = find(nei);
                }
            }
            unordered_map<int, int> cnt;
            for (int u : nodes) cnt[find(u)]++;
            for (auto& [_, c] : cnt) ans += c * (c + 1) / 2;
        }
        return ans;
    }
};
 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
30
31
32
33
34
35
36
37

func numberOfGoodPaths(vals []int, edges [][]int) int {
    n := len(vals)
    g := make([][]int, n)
    for _, e := range edges {
        g[e[0]] = append(g[e[0]], e[1])
        g[e[1]] = append(g[e[1]], e[0])
    }
    val2nodes := map[int][]int{}
    for i, v := range vals {
        val2nodes[v] = append(val2nodes[v], i)
    }
    keys := []int{}
    for k := range val2nodes { keys = append(keys, k) }
    sort.Ints(keys)
    par := make([]int, n)
    for i := range par { par[i] = i }
    var find func(int) int
    find = func(x int) int { if par[x] != x { par[x] = find(par[x]) }; return par[x] }
    ans := 0
    for _, v := range keys {
        for _, u := range val2nodes[v] {
            for _, nei := range g[u] {
                if vals[nei] <= v {
                    par[find(u)] = find(nei)
                }
            }
        }
        cnt := map[int]int{}
        for _, u := range val2nodes[v] {
            cnt[find(u)]++
        }
        for _, c := range cnt {
            ans += c * (c + 1) / 2
        }
    }
    return ans
}
 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
30

class Solution {
    public int numberOfGoodPaths(int[] vals, int[][] edges) {
        int n = vals.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        Map<Integer, List<Integer>> val2nodes = new TreeMap<>();
        for (int i = 0; i < n; i++) val2nodes.computeIfAbsent(vals[i], k -> new ArrayList<>()).add(i);
        int[] par = new int[n];
        for (int i = 0; i < n; i++) par[i] = i;
        java.util.function.IntUnaryOperator find = new java.util.function.IntUnaryOperator() {
            public int applyAsInt(int x) { return par[x] == x ? x : (par[x] = applyAsInt(par[x])); }
        };
        int ans = 0;
        for (int v : val2nodes.keySet()) {
            for (int u : val2nodes.get(v)) {
                for (int nei : g[u]) {
                    if (vals[nei] <= v) par[find.applyAsInt(u)] = find.applyAsInt(nei);
                }
            }
            Map<Integer, Integer> cnt = new HashMap<>();
            for (int u : val2nodes.get(v)) cnt.put(find.applyAsInt(u), cnt.getOrDefault(find.applyAsInt(u), 0) + 1);
            for (int c : cnt.values()) ans += c * (c + 1) / 2;
        }
        return ans;
    }
}
 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

class Solution {
    fun numberOfGoodPaths(vals: IntArray, edges: Array<IntArray>): Int {
        val n = vals.size
        val g = Array(n) { mutableListOf<Int>() }
        for (e in edges) {
            g[e[0]].add(e[1])
            g[e[1]].add(e[0])
        }
        val val2nodes = sortedMapOf<Int, MutableList<Int>>()
        for (i in vals.indices) val2nodes.getOrPut(vals[i]) { mutableListOf() }.add(i)
        val par = IntArray(n) { it }
        fun find(x: Int): Int = if (par[x] == x) x else { par[x] = find(par[x]); par[x] }
        var ans = 0
        for ((v, nodes) in val2nodes) {
            for (u in nodes) {
                for (nei in g[u]) {
                    if (vals[nei] <= v) par[find(u)] = find(nei)
                }
            }
            val cnt = mutableMapOf<Int, Int>()
            for (u in nodes) cnt[find(u)] = cnt.getOrDefault(find(u), 0) + 1
            for (c in cnt.values) ans += c * (c + 1) / 2
        }
        return ans
    }
}
 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

class Solution:
    def numberOfGoodPaths(self, vals: list[int], edges: list[list[int]]) -> int:
        n = len(vals)
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        val2nodes = {}
        for i, v in enumerate(vals):
            val2nodes.setdefault(v, []).append(i)
        par = list(range(n))
        def find(x):
            if par[x] != x:
                par[x] = find(par[x])
            return par[x]
        ans = 0
        for v in sorted(val2nodes):
            for u in val2nodes[v]:
                for nei in g[u]:
                    if vals[nei] <= v:
                        par[find(u)] = find(nei)
            cnt = {}
            for u in val2nodes[v]:
                fu = find(u)
                cnt[fu] = cnt.get(fu, 0) + 1
            for c in cnt.values():
                ans += c * (c + 1) // 2
        return ans
 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
30
31
32
33
34
35
36
37
38
39
40

impl Solution {
    pub fn number_of_good_paths(vals: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
        let n = vals.len();
        let mut g = vec![vec![]; n];
        for e in &edges {
            g[e[0] as usize].push(e[1] as usize);
            g[e[1] as usize].push(e[0] as usize);
        }
        let mut val2nodes = std::collections::BTreeMap::new();
        for (i, &v) in vals.iter().enumerate() {
            val2nodes.entry(v).or_insert(vec![]).push(i);
        }
        let mut par: Vec<_> = (0..n).collect();
        fn find(par: &mut Vec<usize>, x: usize) -> usize {
            if par[x] != x { par[x] = find(par, par[x]); }
            par[x]
        }
        let mut ans = 0;
        for (v, nodes) in val2nodes.iter() {
            for &u in nodes {
                for &nei in &g[u] {
                    if vals[nei] <= *v {
                        let pu = find(&mut par, u);
                        let pn = find(&mut par, nei);
                        par[pu] = pn;
                    }
                }
            }
            let mut cnt = std::collections::HashMap::new();
            for &u in nodes {
                let fu = find(&mut par, u);
                *cnt.entry(fu).or_insert(0) += 1;
            }
            for &c in cnt.values() {
                ans += c * (c + 1) / 2;
            }
        }
        ans as i32
    }
}
 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
30
31
32
33
34
35

class Solution {
    numberOfGoodPaths(vals: number[], edges: number[][]): number {
        const n = vals.length;
        const g: number[][] = Array.from({length: n}, () => []);
        for (const [u, v] of edges) {
            g[u].push(v);
            g[v].push(u);
        }
        const val2nodes: Record<number, number[]> = {};
        for (let i = 0; i < n; i++) {
            if (!val2nodes[vals[i]]) val2nodes[vals[i]] = [];
            val2nodes[vals[i]].push(i);
        }
        const keys = Object.keys(val2nodes).map(Number).sort((a, b) => a - b);
        const par = Array.from({length: n}, (_, i) => i);
        const find = (x: number): number => par[x] === x ? x : (par[x] = find(par[x]));
        let ans = 0;
        for (const v of keys) {
            for (const u of val2nodes[v]) {
                for (const nei of g[u]) {
                    if (vals[nei] <= v) par[find(u)] = find(nei);
                }
            }
            const cnt: Record<number, number> = {};
            for (const u of val2nodes[v]) {
                const fu = find(u);
                cnt[fu] = (cnt[fu] || 0) + 1;
            }
            for (const c of Object.values(cnt)) {
                ans += c * (c + 1) / 2;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n + m), where n is the number of nodes and m is the number of edges; sorting and union-find operations dominate.
  • 🧺 Space complexity: O(n + m), for the graph, parent array, and value groupings.