Number of Good Paths
Hard · Graphs · Explanation and code example
Disjoint Set Union (Union By Value)
How it works
Instead of grouping nodes by value, we can sort the edges by the maximum value of their endpoints. Processing edges in this order ensures that when we connect two components, we only form new good paths when both component representatives have the same value. Each component tracks how many nodes share the maximum value, allowing us to compute new paths during union operations.
Steps
- Initialize a Union-Find where each component tracks the count of nodes with the maximum value in that component.
- Sort edges by the maximum of
vals[u]andvals[v]. - Start with
ngood paths (each node alone is a valid path). - For each edge, union the two endpoints:
- If the representatives have different values, the one with the smaller value gets absorbed.
- If they have equal values, multiply the counts from both sides to get new good paths, then merge.
- Return the total
res.
Complexity
- Time complexity:
O(nlog n) - Space complexity:
O(n)
Things to watch for
Processing Nodes in Wrong Order
The Union-Find solution requires processing nodes or edges in ascending order of their values. Processing in arbitrary order breaks the invariant that when two components merge, all previously processed nodes have smaller or equal values. This leads to incorrect path counts because paths may include nodes with values exceeding the endpoints.
Forgetting Single-Node Paths
Every node by itself forms a valid good path (a path of length 0). The final answer must include n single-node paths in addition to paths between distinct nodes with matching values. Forgetting to add these results in an answer that is exactly n less than correct.
Incorrect Union-Find Merging Logic
When unioning two components with the same maximum value, you must multiply their counts to get new good paths, then sum the counts. When values differ, the component with the smaller maximum value gets absorbed without creating new paths. Confusing these cases or incorrectly updating counts leads to wrong answers.
Double Counting Paths
A path from node A to node B is the same as the path from B to A. When counting paths during BFS/DFS, ensure you only count each pair once. Using the condition node >= startNode when counting matching endpoints prevents counting the same path twice.
Not Using Path Compression in Union-Find
Without path compression, the Union-Find operations can degrade to O(n) per operation, making the overall algorithm O(n^2). Always implement path compression in the find function to maintain near-constant amortized time complexity for Union-Find operations.
Python code example
from typing import List
class DSU:
def __init__(self, n, vals):
self.parent = list(range(n))
self.vals = vals
self.count = [1] * n # count of nodes with max value of the component
def find(self, node):
if self.parent[node] != node:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, u, v):
pu, pv = self.find(u), self.find(v)
if pu == pv:
return 0
if self.vals[pu] < self.vals[pv]:
self.parent[pu] = pv
elif self.vals[pu] > self.vals[pv]:
self.parent[pv] = pu
else:
self.parent[pv] = pu
result = self.count[pu] * self.count[pv]
self.count[pu] += self.count[pv]
return result
return 0
class Solution:
def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
n = len(vals)
dsu = DSU(n, vals)
# Sort edges based on max value of the two nodes
edges.sort(key=lambda edge: max(vals[edge[0]], vals[edge[1]]))
res = n # Each node alone is a good path
for u, v in edges:
res += dsu.union(u, v)
return res
C++ code example
class DSU {
vector<int> parent, count, vals;
public:
DSU(int n, vector<int>& vals) : vals(vals), parent(n), count(n, 1) {
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int node) {
if (parent[node] != node) {
parent[node] = find(parent[node]);
}
return parent[node];
}
int unionNodes(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) {
return 0;
}
if (vals[pu] < vals[pv]) {
parent[pu] = pv;
} else if (vals[pu] > vals[pv]) {
parent[pv] = pu;
} else {
parent[pv] = pu;
int result = count[pu] * count[pv];
count[pu] += count[pv];
return result;
}
return 0;
}
};
class Solution {
public:
int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
int n = vals.size();
DSU dsu(n, vals);
// Sort edges based on max value of the two nodes
sort(edges.begin(), edges.end(), [&](auto& a, auto& b) {
return max(vals[a[0]], vals[a[1]]) < max(vals[b[0]], vals[b[1]]);
});
int res = n; // Each node alone is a good path
for (auto& edge : edges) {
res += dsu.unionNodes(edge[0], edge[1]);
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.