2421. Number of Good Paths - Explanation

1. Brute Force (DFS)

Intuition

A good path starts and ends with nodes having the same value, and all nodes along the path have values less than or equal to that value. For each node, we can run a dfs to explore all reachable nodes where path values stay at or below the starting node's value. We count nodes with the same value as valid endpoints.

Algorithm

Build an adjacency list from the edges.
For each node startNode, run a dfs:
- Only traverse to children with values less than or equal to vals[startNode].
- Count nodes that have the same value as startNode and have index greater than or equal to startNode (to avoid double counting).
Sum up all counts and return the total.

class Solution:
    def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
        n = len(vals)
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        def dfs(node, startNode, parent):
            if vals[node] > vals[startNode]:
                return 0

            res = 0
            if vals[node] == vals[startNode] and node >= startNode:
                res += 1

            for child in adj[node]:
                if child == parent:
                    continue
                res += dfs(child, startNode, node)

            return res


        res = 0
        for node in range(n):
            res += dfs(node, node, -1)
        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$ for recursion stack.

2. Brute Force (BFS)

Intuition

This is the same logic as the dfs approach but uses bfs instead. Starting from each node, we explore all reachable nodes using a queue, only visiting neighbors with values at or below the starting node's value. We count valid endpoints with matching values.

Algorithm

Build an adjacency list from the edges.
For each node startNode, run a bfs:
- Use a queue and a visited set.
- Only add neighbors to the queue if their value is at most vals[startNode].
- Count nodes with the same value as startNode and index at least startNode.
Return the total count.

class Solution:
    def numberOfGoodPaths(self, vals, edges):
        n = len(vals)
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        res = 0
        for startNode in range(n):
            q = deque([startNode])
            visited = set([startNode])
            count = 0

            while q:
                node = q.popleft()
                if vals[node] == vals[startNode] and node >= startNode:
                    count += 1

                for child in adj[node]:
                    if child not in visited and vals[child] <= vals[startNode]:
                        visited.add(child)
                        q.append(child)

            res += count

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

3. Disjoint Set Union

Intuition

Processing nodes in increasing order of their values allows us to incrementally build connected components. When we process nodes with value v, we union them with their neighbors that have values at most v. At each step, nodes with value v in the same component can form good paths with each other. The number of such paths equals the count of same-valued nodes per component.

Algorithm

Group nodes by their values and sort the values in ascending order.
Initialize a Union-Find structure.
For each value (from smallest to largest):
- For each node with this value, union it with neighbors having smaller or equal values.
- Group nodes with the current value by their connected component roots.
- For each component, if k nodes have the current value, add 1 + 2 + ... + k = k*(k+1)/2 to the res (or equivalently, add incrementally).
Return the total res.

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] >= self.Size[pv]:
            self.Size[pu] += self.Size[pv]
            self.Parent[pv] = pu
        else:
            self.Size[pv] += self.Size[pu]
            self.Parent[pu] = pv
        return True

class Solution:
    def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
        adj = collections.defaultdict(list)
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        valToIndex = collections.defaultdict(list)
        for i, val in enumerate(vals):
            valToIndex[val].append(i)

        res = 0
        uf = DSU(len(vals))

        for val in sorted(valToIndex.keys()):
            for i in valToIndex[val]:
                for nei in adj[i]:
                    if vals[nei] <= vals[i]:
                        uf.union(nei, i)

            count = collections.defaultdict(int)
            for i in valToIndex[val]:
                count[uf.find(i)] += 1
                res += count[uf.find(i)]

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Disjoint Set Union (Union By Value)

Intuition

Instead of grouping nodes by value, we can sort the edges by the maximum value of their endpoints. Processing edges in this order ensures that when we connect two components, we only form new good paths when both component representatives have the same value. Each component tracks how many nodes share the maximum value, allowing us to compute new paths during union operations.

Algorithm

Initialize a Union-Find where each component tracks the count of nodes with the maximum value in that component.
Sort edges by the maximum of vals[u] and vals[v].
Start with n good paths (each node alone is a valid path).
For each edge, union the two endpoints:
- If the representatives have different values, the one with the smaller value gets absorbed.
- If they have equal values, multiply the counts from both sides to get new good paths, then merge.
Return the total res.

class DSU:
    def __init__(self, n, vals):
        self.parent = list(range(n))
        self.vals = vals
        self.count = [1] * n # count of nodes with max value of the component

    def find(self, node):
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return 0
        if self.vals[pu] < self.vals[pv]:
            self.parent[pu] = pv
        elif self.vals[pu] > self.vals[pv]:
            self.parent[pv] = pu
        else:
            self.parent[pv] = pu
            result = self.count[pu] * self.count[pv]
            self.count[pu] += self.count[pv]
            return result

        return 0


class Solution:
    def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
        n = len(vals)
        dsu = DSU(n, vals)

        # Sort edges based on max value of the two nodes
        edges.sort(key=lambda edge: max(vals[edge[0]], vals[edge[1]]))

        res = n  # Each node alone is a good path
        for u, v in edges:
            res += dsu.union(u, v)
        return res

Time & Space Complexity

Time complexity: $O(n\log n)$
Space complexity: $O(n)$

Common Pitfalls

Processing Nodes in Wrong Order

The Union-Find solution requires processing nodes or edges in ascending order of their values. Processing in arbitrary order breaks the invariant that when two components merge, all previously processed nodes have smaller or equal values. This leads to incorrect path counts because paths may include nodes with values exceeding the endpoints.

Forgetting Single-Node Paths

Every node by itself forms a valid good path (a path of length 0). The final answer must include n single-node paths in addition to paths between distinct nodes with matching values. Forgetting to add these results in an answer that is exactly n less than correct.

Incorrect Union-Find Merging Logic

When unioning two components with the same maximum value, you must multiply their counts to get new good paths, then sum the counts. When values differ, the component with the smaller maximum value gets absorbed without creating new paths. Confusing these cases or incorrectly updating counts leads to wrong answers.

Double Counting Paths

A path from node A to node B is the same as the path from B to A. When counting paths during BFS/DFS, ensure you only count each pair once. Using the condition node >= startNode when counting matching endpoints prevents counting the same path twice.

Not Using Path Compression in Union-Find

Without path compression, the Union-Find operations can degrade to O(n) per operation, making the overall algorithm O(n^2). Always implement path compression in the find function to maintain near-constant amortized time complexity for Union-Find operations.