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:

  1. The starting and ending nodes must have the same value.
  2. 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:

  1. 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.

  2. 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 node x belongs to, achieving path compression along the way to speed up future queries.
  • union(x, y): Merges the sets that contain x and y, 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, where size[i][v] represents the count of value v in the connected component having root i.
  • An adjacency list g to represent the graph.

Algorithm Steps

  1. Construct the graph from the input edge list.
  2. Sort nodes by their associated values (stored in vals). This allows us to consider possible paths involving smaller or equal values first.
  3. Iterate over the nodes in the sorted order:
    • Consider all the neighbors of current node a. If the neighbor b has a smaller or equal value, we proceed to merge components:
      • Find the roots of a and b using find.
      • 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 that v is the value of current node a) and add it to ans.
      • Perform the union by updating the parent of one root to point to the other and merge the count of value v in the size array.
  4. Return the total number of distinct good paths found, including single-node paths (which contribute n to the initial count of ans).

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 Evaluator

Example 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.

  1. 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.

  2. 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.

  3. 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.
  4. Process node 3:

    • Neighbor 1 was already considered.
    • Neighbor 4 is in the same connected component after processing node 1, so we ignore it.
  5. Process node 4:

    • Neighbors 1 and 3 were already considered.
  6. 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.

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:

  1. Sorting: The given code sorts the nodes based on their values which takes O(n log n) time, where n is the number of nodes.

  2. Union-Find Operations: The disjoint set union-find operations find and union are generally O(alpha(n)) per operation, where alpha(n) is the inverse Ackermann function. This function grows very slowly, practically considered as a constant.

  3. 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 is O(m), where m 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:

  1. Parent Array: The parent array p is of size n which gives a space complexity of O(n).

  2. 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 to n.

  3. Graph and Edges: The graph g which is formed as a dictionary of lists will contain 2 * m entries (since every edge is stored twice, once for each incident node), giving a space complexity of O(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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More