Number of Good Paths
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:
The starting node and the ending node have the same value.
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.
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].
Number of Good Paths Java Solution With Union-Find Approach
class Solution {
public int numberOfGoodPaths(int[] vals, int[][] edges) {
Map> adjacencyList = new HashMap<>();
for(int[] edge : edges){
int nodeA = edge[0];
int nodeB = edge[1];
adjacencyList.computeIfAbsent(nodeA, value -> new ArrayList()).add(nodeB);
adjacencyList.computeIfAbsent(nodeB, value -> new ArrayList()).add(nodeA);
}
int n = vals.length;
TreeMap> map_valuesOfNodes = new TreeMap();
for(int i = 0; i < n; i++){
map_valuesOfNodes.computeIfAbsent(vals[i], value -> new ArrayList()).add(i);
}
UnionFind union = new UnionFind(n);
int noOfgoodPaths = 0;
for(int valueOfNode : map_valuesOfNodes.keySet()){
for(int node : map_valuesOfNodes.get(valueOfNode)){
if(!adjacencyList.containsKey(node)) continue;
for(int nei : adjacencyList.get(node)){
if(vals[node] >= vals[nei]){
union.union(node, nei);
}
}
}
Map group = new HashMap<>();
for(int x : map_valuesOfNodes.get(valueOfNode)){
group.put(union.find(x), group.getOrDefault(union.find(x), 0) +1);
}
for(int key : group.keySet()){
int size = group.get(key);
noOfgoodPaths += size*(size+1)/2;
}
}
return noOfgoodPaths;
}
}
class UnionFind{
int parent[];
int rank[];
public UnionFind(int size){
parent = new int[size];
for(int i = 0; i < size; i++){
parent[i] = i;
rank = new int[size];
}
}
public int find(int x){
if(parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y){
int set_x = find(x);
int set_y = find(y);
if(set_x == set_y){
return;
}
else if(rank[set_x] < rank[set_y]){
parent[set_x] = set_y;
}
else if(rank[set_x] > rank[set_y]){
parent[set_y] = set_x;
}else{
parent[set_y] = set_x;
rank[set_x] ++;
}
}
}
Explanation
This code calculates the number of "good paths" in a graph where each node is associated with a value. A "good path" is defined as a path where all nodes have values less than or equal to the maximum value in the path.
Key Components
adjacencyList: Stores the graph's edges as an adjacency list for efficient traversal.map_valuesOfNodes: ATreeMapthat maps node values to lists of node indices, ensuring values are processed in ascending order.UnionFind: A helper class to manage connected components efficiently using the Union-Find (Disjoint Set Union) algorithm.
Algorithm
Build the adjacency list from the input edges.
Group nodes by their values using
TreeMap, ensuring nodes are processed in ascending order of their values.For each group of nodes with the same value:
For each node, check its neighbors and union nodes with equal or smaller values.
Count the size of each connected component using the
findoperation of Union-Find.Add the number of "good paths" for this value, calculated as
size * (size + 1) / 2.
Return the total number of "good paths."
Union-Find Class
The UnionFind class is a helper class for efficiently managing connected components. It includes methods for:
find: Finds the root of a node, with path compression for efficiency.union: Merges two connected components based on their ranks.
Complexity Analysis
- Time Complexity: O(n log n + m α(n))
Building the adjacency list and
TreeMaptakes O(n log n).Union-Find operations take O(m α(n)), where α(n) is the inverse Ackermann function.
- Space Complexity: O(n + m)
O(n) for Union-Find data structures and
TreeMap.O(m) for the adjacency list.
