Number of Good Paths
HardPrompt
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.
Example 1:
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:
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:
Input: vals = [1], edges = []
Output: 1
Explanation: The tree consists of only one node, so there is one good path.
Constraints:
n == vals.length1 <= n <= 3 * 1040 <= vals[i] <= 105edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedgesrepresents a valid tree.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Build an adjacency list for the graph.
- Initialize
goodPaths = 0. - Iterate through every pair of nodes
(i, j)withi <= j. - If
vals[i] == vals[j]: a. Find the simple path betweeniandjusing BFS or DFS. b. Check if all nodes on the path have values less than or equal tovals[i]. c. If the path is valid, incrementgoodPaths. - Return
goodPaths.
Walkthrough
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.
// 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 BFSprivate 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}Complexity
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.
Trade-offs
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.
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].
Algorithm
- Build an adjacency list for the graph.
- Initialize
goodPaths = n. - Iterate through each node
startNodefrom0ton-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
endNodewherevals[endNode] == vals[startNode]andstartNode < endNode, we've found a new, unique good path. IncrementgoodPaths. - Return
goodPaths.
Walkthrough
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.
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;}Complexity
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.
Trade-offs
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 toB. Later, when starting fromB, we might explore the same path in reverse.
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.
Algorithm
- Build an adjacency list.
- Group nodes by value using a
TreeMapto get sorted unique values. - Initialize a DSU structure with
nsets. - Initialize
goodPaths = n. - Iterate through each
valfrom the sortedTreeMap. - For each node
uwithvals[u] == val: a. For each neighborvofu, ifvals[v] <= val, union the sets ofuandv. - After processing all nodes for the current
val, count the number of nodes with thisvalin each disjoint set. - For each set with
k > 1nodes of the currentval, addk * (k - 1) / 2togoodPaths. - Return
goodPaths.
Walkthrough
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
vin sorted order. - For each node
uwithvals[u] == v:- Iterate through its neighbors
neighborin the original graph. - If
vals[neighbor] <= v, it means the neighbor's component can be connected tou. We perform aunionoperation onuandneighbor. This merges the components they belong to.
- Iterate through its neighbors
- After processing all nodes of value
vand connecting them to their smaller-or-equal-valued neighbors, some of these nodes might now belong to the same connected component. - A new map
groupCountsis used to count how many nodes of the current valuevfall into each component. We iterate through nodesuwithvals[u] == v, find their component's rootr = find(u), and increment the count forr. - For each component root
rthat hask > 1nodes of valuev, it means theseknodes can all reach each other via paths of nodes with values strictly less thanv. This formsk * (k - 1) / 2new good paths. Add this to the totalgoodPaths.
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.
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;}Complexity
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.
Trade-offs
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.
Solutions
Solution
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]; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.