# Number of Good Paths
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-good-paths)
Canonical: https://scaleengineer.com/dsa/problems/number-of-good-paths
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table, Tree, Graph
---
## 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.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-good-paths/image0.png) 

**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:**

![](https://assets.glich.co/dsa/number-of-good-paths/image1.png) 

**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:**

![](https://assets.glich.co/dsa/number-of-good-paths/image2.png) 

**Input:** vals = [1], edges = []
**Output:** 1
**Explanation:** 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.

# Approaches
## Brute-Force Path Search
This approach exhaustively checks every possible pair of nodes in the tree. For each pair `(i, j)`, it first verifies if they have the same value. If they do, it finds the unique simple path between them and then checks if all intermediate nodes on this path have values less than or equal to the value of the start/end nodes.
**Time:** O(N^3), where N is the number of nodes. There are O(N^2) pairs of nodes. For each pair, finding the path and validating it takes O(N) time in a tree. This is too slow for the given constraints. · **Space:** O(N) to store the adjacency list and the path during traversal.
**Pros:** Simple to understand and conceptualize.; Directly implements the definition of a good path.
**Cons:** Extremely inefficient and will time out on larger test cases.; Repeatedly performs pathfinding and validation over the same subpaths.
### Explanation
First, we build an adjacency list representation of the tree from the `edges` array. We initialize a counter for good paths to 0. We iterate through all pairs of nodes `(i, j)` where `i <= j`. If `i == j`, we have a single-node path, which is always good. We increment the counter. If `i < j` and `vals[i] == vals[j]`, we proceed to check the path condition. To find the path, we can use a Depth First Search (DFS) starting from node `i` to find node `j`. During the DFS, we keep track of the current path. Once the path from `i` to `j` is found, we iterate through all the nodes on this path. We check if the value of every intermediate node is less than or equal to `vals[i]`. If this condition holds for the entire path, we've found a good path and increment our counter. After checking all pairs, the counter will hold the total number of good paths.
```java
// This is a conceptual implementation. A full, working version for this approach
// would be complex and is omitted due to its inefficiency.
public int numberOfGoodPaths(int[] vals, int[][] edges) {
    int n = vals.length;
    if (n <= 1) return n;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] edge : edges) {
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }

    int goodPaths = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (vals[i] == vals[j]) {
                if (isGoodPath(i, j, vals, adj)) {
                    goodPaths++;
                }
            }
        }
    }
    return goodPaths;
}

// Helper to find and validate the path using BFS
private boolean isGoodPath(int start, int end, int[] vals, List<List<Integer>> adj) {
    if (start == end) return true;
    
    Queue<List<Integer>> queue = new LinkedList<>();
    List<Integer> initialPath = new ArrayList<>();
    initialPath.add(start);
    queue.add(initialPath);

    boolean[] visited = new boolean[vals.length];
    visited[start] = true;

    while (!queue.isEmpty()) {
        List<Integer> currentPath = queue.poll();
        int lastNode = currentPath.get(currentPath.size() - 1);

        if (lastNode == end) {
            // Path found, now validate
            for (int node : currentPath) {
                if (vals[node] > vals[start]) {
                    return false;
                }
            }
            return true;
        }

        for (int neighbor : adj.get(lastNode)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                List<Integer> newPath = new ArrayList<>(currentPath);
                newPath.add(neighbor);
                queue.add(newPath);
            }
        }
    }
    return false; // Should not be reached in a connected tree
}
```
### Algorithm
*   Build an adjacency list for the graph.
*   Initialize `goodPaths = 0`.
*   Iterate through every pair of nodes `(i, j)` with `i <= j`.
*   If `vals[i] == vals[j]`:
    a. Find the simple path between `i` and `j` using BFS or DFS.
    b. Check if all nodes on the path have values less than or equal to `vals[i]`.
    c. If the path is valid, increment `goodPaths`.
*   Return `goodPaths`.

## Graph Traversal from Each Node
This approach improves upon the brute-force method by avoiding the explicit check of all pairs. Instead, for each node `u`, it initiates a graph traversal (like BFS or DFS) to find all other reachable nodes `v` that could form a good path with `u`. The traversal is constrained: it can only move to neighbors with values less than or equal to `vals[u]`.
**Time:** O(N^2), where N is the number of nodes. The outer loop runs N times. Inside the loop, the traversal can visit up to N nodes and N-1 edges in the worst case. · **Space:** O(N) for the adjacency list, the queue/recursion stack for traversal, and a visited set.
**Pros:** More efficient than the O(N^3) brute-force approach.; The logic is still relatively straightforward, building upon standard graph traversal algorithms.
**Cons:** Still too slow for the given constraints.; It recomputes information. For example, when starting a traversal from node `A`, we might find a path to `B`. Later, when starting from `B`, we might explore the same path in reverse.
### Explanation
First, we build an adjacency list for the tree. We initialize the total number of good paths to `n`, accounting for all single-node paths. We then iterate through each node `u` from `0` to `n-1`. For each `u`, we start a traversal (e.g., BFS). The key idea is to prune the search space. From a node `curr`, we only explore a `neighbor` if `vals[neighbor] <= vals[u]`. During this traversal, if we encounter a node `v` such that `vals[v] == vals[u]`, we have found a valid good path. This is because all nodes visited to reach `v` from `u` must have values less than or equal to `vals[u]`. To avoid double-counting paths (since a path `u -> v` is the same as `v -> u`), we only increment our count if `u < v`.
```java
public int numberOfGoodPaths(int[] vals, int[][] edges) {
    int n = vals.length;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }

    int goodPaths = n; // Each single node is a good path

    for (int i = 0; i < n; i++) {
        // Start a traversal from node i
        Queue<Integer> q = new LinkedList<>();
        q.add(i);
        Set<Integer> visited = new HashSet<>();
        visited.add(i);

        while (!q.isEmpty()) {
            int u = q.poll();

            for (int v : adj.get(u)) {
                if (!visited.contains(v) && vals[v] <= vals[i]) {
                    visited.add(v);
                    if (vals[v] == vals[i]) {
                        // To avoid double counting, only count if i < v
                        if (i < v) {
                            goodPaths++;
                        }
                    }
                    q.add(v);
                }
            }
        }
    }
    return goodPaths;
}
```
### Algorithm
*   Build an adjacency list for the graph.
*   Initialize `goodPaths = n`.
*   Iterate through each node `startNode` from `0` to `n-1`.
*   Perform a graph traversal (BFS or DFS) starting from `startNode`.
*   The traversal is restricted: from a current node, only visit neighbors whose value is less than or equal to `vals[startNode]`.
*   During the traversal, if we reach a node `endNode` where `vals[endNode] == vals[startNode]` and `startNode < endNode`, we've found a new, unique good path. Increment `goodPaths`.
*   Return `goodPaths`.

## Union-Find on Sorted Node Values
This is an efficient approach that processes nodes in increasing order of their values. It uses a Disjoint Set Union (DSU) or Union-Find data structure to keep track of connected components of nodes that have values less than or equal to the current value being processed. By merging components and counting nodes of the same value within the newly formed components, we can efficiently count all good paths.
**Time:** O(N log N). Sorting the values (implicitly done by `TreeMap` or explicitly) takes O(N log N). The main loop iterates through unique values. The nested loops iterate through all nodes and edges once in total across all values. The DSU operations with path compression and union by rank/size are nearly constant, O(α(N)), where α is the inverse Ackermann function. The dominant factor is sorting the values or nodes. · **Space:** O(N) to store the adjacency list, the `valToNodes` map, and the DSU data structure.
**Pros:** Highly efficient and passes the given constraints.; Elegantly solves the problem by changing the perspective from pathfinding to component building.
**Cons:** More complex to understand and implement compared to direct traversal methods.; Requires knowledge of the Union-Find data structure.
### Explanation
The core idea is to build the graph incrementally. We consider nodes from the smallest value to the largest. When we "add" nodes of a certain value `v`, we connect them to any adjacent, already-existing components (which are guaranteed to have nodes with values smaller than `v`).

**Initialization:**
*   Start with `goodPaths = n` (for single-node paths).
*   Create an adjacency list.
*   Group nodes by their value into a map: `valToNodes`.
*   Get a sorted list of unique values present in the graph.
*   Initialize a DSU structure where each node is in its own set.

**Processing:**
*   Iterate through the unique values `v` in sorted order.
*   For each node `u` with `vals[u] == v`:
    *   Iterate through its neighbors `neighbor` in the original graph.
    *   If `vals[neighbor] <= v`, it means the neighbor's component can be connected to `u`. We perform a `union` operation on `u` and `neighbor`. This merges the components they belong to.
*   After processing all nodes of value `v` and connecting them to their smaller-or-equal-valued neighbors, some of these nodes might now belong to the same connected component.
*   A new map `groupCounts` is used to count how many nodes of the current value `v` fall into each component. We iterate through nodes `u` with `vals[u] == v`, find their component's root `r = find(u)`, and increment the count for `r`.
*   For each component root `r` that has `k > 1` nodes of value `v`, it means these `k` nodes can all reach each other via paths of nodes with values strictly less than `v`. This forms `k * (k - 1) / 2` new good paths. Add this to the total `goodPaths`.

This process ensures that when we count paths between nodes of value `v`, all intermediate nodes on the path have values strictly less than `v`, satisfying the good path condition.
```java
class DSU {
    int[] parent;
    public DSU(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }
    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // A simple union, could be optimized with union by size/rank
            parent[rootJ] = rootI;
        }
    }
}

public int numberOfGoodPaths(int[] vals, int[][] edges) {
    int n = vals.length;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] edge : edges) {
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }

    TreeMap<Integer, List<Integer>> valToNodes = new TreeMap<>();
    for (int i = 0; i < n; i++) {
        valToNodes.computeIfAbsent(vals[i], k -> new ArrayList<>()).add(i);
    }

    DSU dsu = new DSU(n);
    int goodPaths = n;

    for (int val : valToNodes.keySet()) {
        // Union nodes with their neighbors that have smaller or equal values
        for (int u : valToNodes.get(val)) {
            for (int v : adj.get(u)) {
                if (vals[v] <= vals[u]) {
                    dsu.union(u, v);
                }
            }
        }
        
        // Count nodes of the current value in each component
        Map<Integer, Integer> groupCounts = new HashMap<>();
        for (int u : valToNodes.get(val)) {
            int root = dsu.find(u);
            groupCounts.put(root, groupCounts.getOrDefault(root, 0) + 1);
        }

        // Calculate new good paths
        for (int count : groupCounts.values()) {
            goodPaths += (count * (count - 1)) / 2;
        }
    }

    return goodPaths;
}
```
### Algorithm
*   Build an adjacency list.
*   Group nodes by value using a `TreeMap` to get sorted unique values.
*   Initialize a DSU structure with `n` sets.
*   Initialize `goodPaths = n`.
*   Iterate through each `val` from the sorted `TreeMap`.
*   For each node `u` with `vals[u] == val`:
    a. For each neighbor `v` of `u`, if `vals[v] <= val`, union the sets of `u` and `v`.
*   After processing all nodes for the current `val`, count the number of nodes with this `val` in each disjoint set.
*   For each set with `k > 1` nodes of the current `val`, add `k * (k - 1) / 2` to `goodPaths`.
*   Return `goodPaths`.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  int numberOfGoodPaths(int[] vals, int[][] edges) {
    int n = vals.length;
    p = new int[n];
    int[][] arr = new int[n][2];
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (int[] e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    Map<Integer, Map<Integer, Integer>> size = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      p[i] = i;
      arr[i] = new int[]{vals[i], i};
      size.computeIfAbsent(i, k->new HashMap<>()).put(vals[i], 1);
    }
    Arrays.sort(arr, (a, b)->a[0] - b[0]);
    int ans = n;
    for (var e : arr) {
      int v = e[0], a = e[1];
      for (int b : g[a]) {
        if (vals[b] > v) {
          continue;
        }
        int pa = find(a), pb = find(b);
        if (pa != pb) {
          ans +=
              size.get(pa).getOrDefault(v, 0) * size.get(pb).getOrDefault(v, 0);
          p[pa] = pb;
          size.get(pb).put(v, size.get(pb).getOrDefault(v, 0) +
                                  size.get(pa).getOrDefault(v, 0));
        }
      }
    }
    return ans;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfGoodPaths(vector<int> &vals, vector<vector<int>> &edges) {
    int n = vals.size();
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find;
    find = [&](int x) {
      if (p[x] != x) {
        p[x] = find(p[x]);
      }
      return p[x];
    };
    vector<vector<int>> g(n);
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      g[b].push_back(a);
    }
    unordered_map<int, unordered_map<int, int>> size;
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; ++i) {
      arr[i] = {vals[i], i};
      size[i][vals[i]] = 1;
    }
    sort(arr.begin(), arr.end());
    int ans = n;
    for (auto [v, a] : arr) {
      for (int b : g[a]) {
        if (vals[b] > v) {
          continue;
        }
        int pa = find(a), pb = find(b);
        if (pa != pb) {
          ans += size[pa][v] * size[pb][v];
          p[pa] = pb;
          size[pb][v] += size[pa][v];
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
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

```