2421. Number of Good Paths
Problem Description
In this problem, we are given a connected, undirected graph without cycles (a tree) with n
nodes, numbered 0
to n - 1
, as well as n - 1
edges connecting them. Each node has an associated integer value given in the array vals
.
We are tasked with finding the number of "good paths" in the tree. A "good path" is defined by the following conditions:
- The starting and ending nodes must have the same value.
- All intermediate nodes on the path must have values less than or equal to the value of the starting/ending nodes.
The problem asks for the total count of such unique paths. Duplicate paths are not counted separately, which means that reverse paths (e.g., 1 -> 2
and 2 -> 1
) are considered the same. It is also mentioned that a single node by itself counts as a valid path.
Intuition
The solution uses the Disjoint Set Union (DSU) or Union-Find algorithm to keep track of which nodes are in the same connected component as the algorithm processes each node.
The strategy is to consider the nodes in non-decreasing order of their values, which guarantees that when we are processing paths starting/ending at a node with value v
, all possible intermediate nodes (those with values less than or equal to v
) have already been considered.
For each node, the algorithm does the following:
-
Looks at each neighboring node. If a neighbor's value is greater than the current node's value, we ignore it for now because it cannot be part of a good path that starts/ends with the current node's value.
-
If a neighbor's value is less than or equal to the current node's value, we take the following steps:
- Find the roots of the current node and the neighbor using the "find" function from the Union-Find algorithm to determine if they are in separate components.
- If they are in separate components, we merge these components and calculate the product of the counts of matching values from both components. This product represents the additional good paths that can be formed by joining these two components.
- Update the DSU to reflect the merge and accumulate the count for
v
in the larger component.
By considering nodes in non-decreasing order of their values and using DSU to keep track of components and their counts of equal values, we can systematically build good paths throughout the tree and eventually return the total count of good paths.
Learn more about Tree, Union Find and Graph patterns.
Solution Approach
The solution to the problem makes good use of the Disjoint Set Union (DSU) or Union-Find data structure along with a strategy to process nodes in a particular order.
Union-Find (Disjoint Set Union)
The Union-Find data structure is crucial to this solution. We initialize each node to be its own parent to denote that each node is in its own set. The two core functions of this algorithm are find
and union
:
find(x)
: Recursively locates the root of a set that the nodex
belongs to, achieving path compression along the way to speed up future queries.union(x, y)
: Merges the sets that containx
andy
, by linking one root to another. In our implementation, when we union two sets, we also merge the counts of each value within the sets.
Data Structures
- An array
p
to store the parent of each node, used by the DSU. - A dictionary of counters,
size
, wheresize[i][v]
represents the count of valuev
in the connected component having rooti
. - An adjacency list
g
to represent the graph.
Algorithm Steps
- Construct the graph from the input edge list.
- Sort nodes by their associated values (stored in
vals
). This allows us to consider possible paths involving smaller or equal values first. - Iterate over the nodes in the sorted order:
- Consider all the neighbors of current node
a
. If the neighborb
has a smaller or equal value, we proceed to merge components:- Find the roots of
a
andb
usingfind
. - If they have different roots (i.e., are in different components), we calculate the number of new good paths formed by this potential merge, which is the product
size[pa][v] * size[pb][v]
(considering thatv
is the value of current nodea
) and add it toans
. - Perform the
union
by updating the parent of one root to point to the other and merge the count of valuev
in thesize
array.
- Find the roots of
- Consider all the neighbors of current node
- Return the total number of distinct good paths found, including single-node paths (which contribute
n
to the initial count ofans
).
Using the above approach, the algorithm efficiently calculates the total number of good paths by gradually considering larger paths as it iterates through nodes by increasing value, while tracking connected components and the counts of values within them via DSU.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Consider a graph (tree) with 5 nodes with the following edges and node values:
Nodes: 0 1 2 3 4 Values: 4 3 4 3 3 Edges: {0-1, 1-2, 1-3, 3-4}
This can be visualized as:
4(0) | 3(1) /| \ 4(2) 3(3)--3(4)
We initialize each node as its own parent, representing each node as a separate component.
-
Sort nodes by their values: (1, 3, 4), (2, 4), (0, 4). Since nodes 1, 3, and 4 have the same value, any order among them is fine for the algorithm.
-
We start with the nodes of value 3 which are nodes 1, 3, and 4. The initial number of good paths is 5, since each node by itself is a valid path.
-
Process node 1:
- Look at neighbor 0 (value 4), ignore it as it's larger.
- Look at neighbor 2 (value 4), ignore it as it's larger.
- Look at neighbors 3 and 4 (value 3). Find their roots (all are their own roots at the start), and since they're separate components, merge them. We count this as a good path, so now we have 6 good paths.
-
Process node 3:
- Neighbor 1 was already considered.
- Neighbor 4 is in the same connected component after processing node 1, so we ignore it.
-
Process node 4:
- Neighbors 1 and 3 were already considered.
-
Now, the nodes with value 4, nodes 0 and 2:
- Process node 0:
- Neighbor 1 has a smaller value; find(1) is 1, find(0) is 0, which are in separate components. We union them and we get 1 additional path: (0-1). Now we have 7 good paths.
- Process node 2:
- Neighbor 1 has a smaller value; find(1) is now the same as find(0) due to the previous union, so they are no longer separate and we don't add any new paths.
- Process node 0:
In the end, we have a total of 7 good paths. The paths are the 5 single-node paths and the 2 multi-node paths (1-3-4) and (0-1).
Solution Implementation
1from collections import defaultdict, Counter
2
3class Solution:
4 def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
5 # Finds the root of the set to which 'x' belongs and performs path compression
6 def find(x):
7 if parent[x] != x:
8 parent[x] = find(parent[x])
9 return parent[x]
10
11 # Constructs a graph using an adjacency list representation
12 graph = defaultdict(list)
13 for a, b in edges:
14 graph[a].append(b)
15 graph[b].append(a)
16
17 node_count = len(vals)
18 parent = list(range(node_count)) # Initially sets each node as its own parent
19 size = defaultdict(Counter) # Will keep track of the size of each value group
20
21 # Initialize the size counter for each node and its corresponding value
22 for i, value in enumerate(vals):
23 size[i][value] = 1
24
25 good_path_count = node_count # Starts with the number of individual nodes as good paths
26
27 # Sorts nodes by their values along with their indices for processing
28 for value, node in sorted(zip(vals, range(node_count))):
29 # Considers adjacent nodes
30 for neighbor in graph[node]:
31 # Skips over any neighbor whose value is larger
32 if vals[neighbor] > value:
33 continue
34 # Finds parent representatives of both sets
35 parent_a, parent_b = find(node), find(neighbor)
36 # Merge sets if they are different
37 if parent_a != parent_b:
38 # Increment the count of good paths based on the sizes of mergeable groups
39 good_path_count += size[parent_a][value] * size[parent_b][value]
40 parent[parent_a] = parent_b # Union the sets by updating the parent
41 size[parent_b][value] += size[parent_a][value] # Update the size of the value group
42
43 return good_path_count # Returns the total number of good paths
44
1class Solution {
2 // Parent array for union-find structure
3 private int[] parent;
4
5 // Method to calculate the number of good paths
6 public int numberOfGoodPaths(int[] vals, int[][] edges) {
7 int n = vals.length; // Number of vertices
8 parent = new int[n]; // Initialize the parent array for union-find
9 int[][] valueIndexPairs = new int[n][2]; // Array to hold value and index pairs
10 List<Integer>[] graph = new List[n]; // Adjacency list for graph representation
11 Arrays.setAll(graph, k -> new ArrayList<>()); // Initialize the adjacency list
12 for (int[] edge : edges) {
13 // Add the edge to graph
14 int a = edge[0], b = edge[1];
15 graph[a].add(b);
16 graph[b].add(a);
17 }
18
19 // Map to keep track of component sizes with specific values
20 Map<Integer, Map<Integer, Integer>> componentSize = new HashMap<>();
21
22 for (int i = 0; i < n; ++i) {
23 parent[i] = i; // Make each vertex its own parent initially
24 valueIndexPairs[i] = new int[] {vals[i], i}; // Create pairs of value and its index
25 // Initialize the component size map
26 componentSize.computeIfAbsent(i, k -> new HashMap<>()).put(vals[i], 1);
27 }
28
29 // Sort the valueIndexPairs based on values
30 Arrays.sort(valueIndexPairs, (a, b) -> a[0] - b[0]);
31
32 int ans = n; // Initialize count of good paths (every vertex is a trivial good path)
33 for (var pair : valueIndexPairs) {
34 int value = pair[0], vertexIndex = pair[1];
35 for (int neighbor : graph[vertexIndex]) {
36 // Skip the neighbor vertices that have a greater value
37 if (vals[neighbor] > value) {
38 continue;
39 }
40 // Find the parents of the current vertex and the neighbor
41 int setA = find(vertexIndex), setB = find(neighbor);
42 if (setA != setB) {
43 // Combine sizes of the components if they have the same vertex value
44 ans += componentSize.get(setA).getOrDefault(value, 0) * componentSize.get(setB).getOrDefault(value, 0);
45 parent[setA] = setB; // Union the two sets
46 // Merge the size maps after performing the union
47 int sizeSum = componentSize.get(setB).getOrDefault(value, 0) + componentSize.get(setA).getOrDefault(value, 0);
48 componentSize.get(setB).put(value, sizeSum);
49 }
50 }
51 }
52 return ans;
53 }
54
55 // Find method with path compression for union-find
56 private int find(int x) {
57 if (parent[x] != x) {
58 parent[x] = find(parent[x]); // Path compression step
59 }
60 return parent[x];
61 }
62}
63
1#include <vector>
2#include <unordered_map>
3#include <numeric>
4#include <algorithm>
5#include <functional>
6
7using namespace std;
8
9class Solution {
10public:
11 int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
12 int n = vals.size(); // number of vertices
13 vector<int> parents(n);
14 iota(parents.begin(), parents.end(), 0); // initialize parents
15
16 // Function to find the root of a set with path compression.
17 function<int(int)> find = [&](int x) {
18 if (parents[x] != x) {
19 parents[x] = find(parents[x]);
20 }
21 return parents[x];
22 };
23
24 vector<vector<int>> graph(n); // adjacency list for the graph
25 for (auto& edge : edges) {
26 int a = edge[0], b = edge[1];
27 graph[a].push_back(b);
28 graph[b].push_back(a);
29 }
30
31 unordered_map<int, unordered_map<int, int>> setSize;
32 vector<pair<int, int>> valIndexPairs(n);
33
34 // Initialize the valIndexPairs and setSize data structures.
35 for (int i = 0; i < n; ++i) {
36 valIndexPairs[i] = {vals[i], i};
37 setSize[i][vals[i]] = 1;
38 }
39 sort(valIndexPairs.begin(), valIndexPairs.end()); // sort the valIndexPairs based on vals
40
41 int answer = n; // start with n good paths, each vertex is a trivial good path
42 for (auto& [value, vertex] : valIndexPairs) {
43 // For all neighbors, perform union-find operation.
44 for (int neighbour : graph[vertex]) {
45 if (vals[neighbour] > value) {
46 continue; // only consider non-decreasing paths
47 }
48 int rootVertex = find(vertex), rootNeighbour = find(neighbour);
49 if (rootVertex != rootNeighbour) {
50 // Combine the sets and update the number of good paths.
51 answer += setSize[rootVertex][value] * setSize[rootNeighbour][value];
52 parents[rootVertex] = rootNeighbour; // union the two sets
53 setSize[rootNeighbour][value] += setSize[rootVertex][value]; // update set size
54 }
55 }
56 }
57
58 return answer;
59 }
60};
61
1const vals: number[] = [];
2const edges: number[][] = [];
3let parents: number[] = [];
4let graph: number[][] = [];
5let setSize: Map<number, Map<number, number>> = new Map();
6
7// Function to find the root of a set with path compression.
8function find(x: number): number {
9 if (parents[x] !== x) {
10 parents[x] = find(parents[x]);
11 }
12 return parents[x];
13}
14
15// Function to compute the number of good paths.
16function numberOfGoodPaths(vals: number[], edges: number[][]): number {
17 const n: number = vals.length; // number of vertices
18 parents = Array.from({length: n}, (_, index) => index); // initialize parents with their own indices
19
20 graph = Array.from({length: n}, () => []); // create an empty adjacency list for the graph
21 edges.forEach(edge => {
22 const [a, b] = edge;
23 graph[a].push(b);
24 graph[b].push(a);
25 });
26
27 // Initialize with each node as its own set containing only its value.
28 for (let i = 0; i < n; i++) {
29 if (!setSize.has(i)) {
30 setSize.set(i, new Map());
31 }
32 setSize.get(i)!.set(vals[i], 1);
33 }
34
35 // Pairs of value and index, sorted by value.
36 const valIndexPairs: [number, number][] = vals.map((value, index) => [value, index]);
37 valIndexPairs.sort((a, b) => a[0] - b[0]);
38
39 let answer = n; // Start with n good paths, as each vertex is a trivial good path.
40
41 valIndexPairs.forEach(([value, vertex]) => {
42 graph[vertex].forEach(neighbour => {
43 if (vals[neighbour] > value) {
44 return; // skip if path is not non-decreasing
45 }
46 const rootVertex = find(vertex);
47 const rootNeighbour = find(neighbour);
48 if (rootVertex !== rootNeighbour) {
49 // Combine sets and update the number of good paths.
50 const setSizeVertex = setSize.get(rootVertex)!.get(value) || 0;
51 const setSizeNeighbour = setSize.get(rootNeighbour)!.get(value) || 0;
52 answer += setSizeVertex * setSizeNeighbour;
53
54 // Union the two sets.
55 parents[rootVertex] = rootNeighbour;
56
57 // Update set size.
58 setSize.get(rootNeighbour)!.set(value, setSizeVertex + setSizeNeighbour);
59 }
60 });
61 });
62
63 return answer;
64}
65
Time and Space Complexity
Time Complexity
The time complexity of the given code is determined by several components:
-
Sorting: The given code sorts the nodes based on their values which takes
O(n log n)
time, wheren
is the number of nodes. -
Union-Find Operations: The disjoint set union-find operations find and union are generally
O(alpha(n))
per operation, wherealpha(n)
is the inverse Ackermann function. This function grows very slowly, practically considered as a constant. -
Processing Edges and Nodes: During the processing of each node, each of its edges is checked for whether it should be considered for union, based on the values at the nodes it connects. In the worst case, each node is connected to every other node, which would result in
O(n)
operations per node. However, since each edge is considered exactly once (being an undirected graph), the complexity due to this isO(m)
, wherem
is the number of edges.
Combining all these, the total worst-case time complexity can be seen as O(n log n + (m + n) * alpha(n))
. Assuming the inverse Ackermann function is practically constant, this simplifies to O(n log n + m)
.
Space Complexity
Let's consider the space complexity components:
-
Parent Array: The parent array
p
is of sizen
which gives a space complexity ofO(n)
. -
Size Dictionary: The
size
dictionary contains counters for the values at each node. This could, in the worst case, contain every value for each representative of a connected component, but since values are fixed and each node connects to edges, the total unique entries will be limited ton
. -
Graph and Edges: The graph
g
which is formed as a dictionary of lists will contain2 * m
entries (since every edge is stored twice, once for each incident node), giving a space complexity ofO(m)
.
Hence, the total space complexity is O(n + m)
since these are the largest contributing factors.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Want a Structured Path to Master System Design Too? Donāt Miss This!