How do you solve Number of Good Paths on LeetCode?

Number of Good Paths (LeetCode #2421) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Using Union-Find helps efficiently manage connected components.

What is the brute force solution for Number of Good Paths?

The brute force approach for Number of Good Paths is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking all possible paths in the tree to see if they meet the criteria for being a good path. This is straightforward but inefficient, as it requires examining each pair of nodes and their connecting paths. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Number of Good Paths?

Number of Good Paths uses the following concepts: Array, Hash Table, Tree, Union-Find, Graph Theory, Sorting. The recommended patterns to study are: Union-Find, Graph Traversal.

What are the interview tips for Number of Good Paths?

Explain your thought process clearly while coding. Discuss edge cases, such as trees with only one node. Practice explaining the Union-Find structure and its operations.

What are common mistakes when solving Number of Good Paths?

Not considering single-node paths as valid. Failing to account for the maximum value condition on paths.

#2421

Number of Good Paths

Hard

ArrayHash TableTreeUnion-FindGraph TheorySortingUnion-FindGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal solution leverages sorting and Union-Find to efficiently group nodes by their values. By processing nodes from the smallest to the largest value, we can dynamically connect nodes and count good paths without redundant checks.

⚙️

Algorithm

4 steps

1Step 1: Create a Union-Find structure to manage connected components of nodes.
2Step 2: Sort nodes based on their values.
3Step 3: For each node, connect it with its neighbors if their values are less than or equal to the current node's value.
4Step 4: Count good paths by checking the size of each component formed by nodes with the same value.

solution.py50 lines

1# Full working Python code
2class UnionFind:
3    def __init__(self, size):
4        self.parent = list(range(size))
5        self.rank = [1] * size
6
7    def find(self, u):
8        if self.parent[u] != u:
9            self.parent[u] = self.find(self.parent[u])
10        return self.parent[u]
11
12    def union(self, u, v):
13        rootU = self.find(u)
14        rootV = self.find(v)
15        if rootU != rootV:
16            if self.rank[rootU] > self.rank[rootV]:
17                self.parent[rootV] = rootU
18            elif self.rank[rootU] < self.rank[rootV]:
19                self.parent[rootU] = rootV
20            else:
21                self.parent[rootV] = rootU
22                self.rank[rootU] += 1
23
24def countGoodPaths(vals, edges):
25    n = len(vals)
26    uf = UnionFind(n)
27    graph = [[] for _ in range(n)]
28    for a, b in edges:
29        graph[a].append(b)
30        graph[b].append(a)
31
32    indexed_vals = sorted(range(n), key=lambda i: vals[i])
33    count = 0
34    freq = defaultdict(int)
35
36    for node in indexed_vals:
37        freq[vals[node]] += 1
38        for neighbor in graph[node]:
39            if vals[neighbor] <= vals[node]:
40                uf.union(node, neighbor)
41
42        component_size = defaultdict(int)
43        for i in range(n):
44            root = uf.find(i)
45            component_size[root] += 1
46
47        for size in component_size.values():
48            count += size * (size + 1) // 2
49
50    return count

ℹ

Complexity note: The complexity is O(n log n) due to the sorting step, while the Union-Find operations are nearly constant time, leading to efficient path counting.

1Using Union-Find helps efficiently manage connected components.
2Sorting nodes by values allows us to build paths incrementally.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.