Number of Good Paths — Solution in Python, Java & C++
Number of Good Paths solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and sorting.
Number of Good Paths is a hard coding problem on arrays, sorting and trees, asked in Amazon, Google and Uber interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Trees, Graph, Union Find
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A tree of n nodes has value vals[i] on node i. A good path is a simple path where the two endpoints carry the same value and no node strictly between them carries a larger one.
Return the number of good paths. A single node is a good path of length 0, and a path and its reverse count once.
Example 1
Input: vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
Output: 6
Explanation: The five single nodes, plus `1 → 0 → 2 → 3`.
Example 2
Input: vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]
Output: 7
Example 3
Input: vals = [1], edges = []
Output: 1
Explanation: One node is one good path.
Constraints
n == vals.length1 <= n <= 300000 <= vals[i] <= 100000edges.length == n - 1edges[i].length == 20 <= edges[i][0], edges[i][1] < nedges represents a valid tree
Hints for Number of Good Paths
Hint 1
Add the edges in increasing order of the larger of their two endpoint values.
Hint 2
At every moment, each union-find component is a region where every node is at most the current threshold.
Hint 3
When two components whose maxima are equal merge, every pair of their maximum-valued nodes forms a good path.
How to solve Number of Good Paths
Grow the tree edge by edge in increasing order of max(vals[u], vals[v]). Track, per component, its maximum value and how many nodes hold it. When two components with equal maxima join, they contribute cntA · cntB new good paths.
Approach
- Start with every node its own component:
best = vals[i],cnt = 1, and an answer ofnfor the single-node paths. - Sort the edges by the larger endpoint value and union them in that order.
- If the two components' maxima are equal, add
cntA · cntBand keep the combined count; otherwise keep only the larger side's maximum and count.
Why it works
The sorted order guarantees every node already merged is at most the current threshold, so nothing on the path between two maximum-valued nodes can exceed them — which is exactly the good-path condition. Pairs are counted at the moment two components merge, which is the first time such a path exists, so nothing is double counted.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- The
nsingle-node paths are part of the answer. - When the maxima differ, the smaller side's count is discarded, not added.
- Sorting by a single endpoint rather than by the larger one lets a bigger value sneak into the middle of a path.
Reference solution
Python
from typing import List
def numberOfGoodPaths(vals: List[int], edges: List[List[int]]) -> int:
n = len(vals)
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
best = vals[:]
cnt = [1] * n
ans = n
for u, v in sorted(edges, key=lambda e: max(vals[e[0]], vals[e[1]])):
ru, rv = find(u), find(v)
if ru == rv:
continue
if best[ru] == best[rv]:
ans += cnt[ru] * cnt[rv]
new_best, new_cnt = best[ru], cnt[ru] + cnt[rv]
elif best[ru] > best[rv]:
new_best, new_cnt = best[ru], cnt[ru]
else:
new_best, new_cnt = best[rv], cnt[rv]
parent[rv] = ru
best[ru] = new_best
cnt[ru] = new_cnt
return ansJava
private static int[] gpParent;
private static int gpFind(int x) {
while (gpParent[x] != x) {
gpParent[x] = gpParent[gpParent[x]];
x = gpParent[x];
}
return x;
}
public static int numberOfGoodPaths(int[] vals, int[][] edges) {
int n = vals.length;
gpParent = new int[n];
for (int i = 0; i < n; i++) gpParent[i] = i;
int[] best = vals.clone();
int[] cnt = new int[n];
Arrays.fill(cnt, 1);
int[][] sorted = edges.clone();
Arrays.sort(sorted, (a, b) ->
Math.max(vals[a[0]], vals[a[1]]) - Math.max(vals[b[0]], vals[b[1]]));
int ans = n;
for (int[] e : sorted) {
int ru = gpFind(e[0]), rv = gpFind(e[1]);
if (ru == rv) continue;
int newBest, newCnt;
if (best[ru] == best[rv]) {
ans += cnt[ru] * cnt[rv];
newBest = best[ru];
newCnt = cnt[ru] + cnt[rv];
} else if (best[ru] > best[rv]) {
newBest = best[ru];
newCnt = cnt[ru];
} else {
newBest = best[rv];
newCnt = cnt[rv];
}
gpParent[rv] = ru;
best[ru] = newBest;
cnt[ru] = newCnt;
}
return ans;
}C++
int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
int n = (int) vals.size();
vector<int> parent(n);
for (int i = 0; i < n; i++) parent[i] = i;
function<int(int)> find = [&](int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
vector<int> best = vals, cnt(n, 1);
vector<vector<int>> sorted = edges;
sort(sorted.begin(), sorted.end(), [&](const vector<int>& a, const vector<int>& b) {
return max(vals[a[0]], vals[a[1]]) < max(vals[b[0]], vals[b[1]]);
});
int ans = n;
for (auto& e : sorted) {
int ru = find(e[0]), rv = find(e[1]);
if (ru == rv) continue;
int newBest, newCnt;
if (best[ru] == best[rv]) {
ans += cnt[ru] * cnt[rv];
newBest = best[ru];
newCnt = cnt[ru] + cnt[rv];
} else if (best[ru] > best[rv]) {
newBest = best[ru];
newCnt = cnt[ru];
} else {
newBest = best[rv];
newCnt = cnt[rv];
}
parent[rv] = ru;
best[ru] = newBest;
cnt[ru] = newCnt;
}
return ans;
}JavaScript
var numberOfGoodPaths = function(vals, edges) {
var n = vals.length, i;
var parent = [];
for (i = 0; i < n; i++) parent.push(i);
var find = function(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
var best = vals.slice();
var cnt = [];
for (i = 0; i < n; i++) cnt.push(1);
var sorted = edges.slice();
sorted.sort(function(a, b) {
return Math.max(vals[a[0]], vals[a[1]]) - Math.max(vals[b[0]], vals[b[1]]);
});
var ans = n;
for (i = 0; i < sorted.length; i++) {
var ru = find(sorted[i][0]), rv = find(sorted[i][1]);
if (ru === rv) continue;
var newBest, newCnt;
if (best[ru] === best[rv]) {
ans += cnt[ru] * cnt[rv];
newBest = best[ru];
newCnt = cnt[ru] + cnt[rv];
} else if (best[ru] > best[rv]) {
newBest = best[ru];
newCnt = cnt[ru];
} else {
newBest = best[rv];
newCnt = cnt[rv];
}
parent[rv] = ru;
best[ru] = newBest;
cnt[ru] = newCnt;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms