Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2505. Number of Good Paths

My accepted Python solution to LeetCode problem 2505, Number of Good Paths, running in 403ms.

  • Difficulty: Hard
  • Python
  • Runtime 403ms
  • Memory 36MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 403ms, memory 36MB, accepted 2025-12-29.

python
class Solution:
    def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
        from collections import defaultdict
        
        n = len(vals)
        
        # Build adjacency list
        adj = defaultdict(list)
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        
        # Union-Find
        parent = list(range(n))
        rank = [0] * n
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
        
        # Group nodes by their values
        val_to_nodes = defaultdict(list)
        for i, v in enumerate(vals):
            val_to_nodes[v].append(i)
        
        result = n  # Each node is a valid path by itself
        
        # Process nodes in increasing order of values
        for val in sorted(val_to_nodes.keys()):
            # Union nodes with neighbors having value <= val
            for node in val_to_nodes[val]:
                for neighbor in adj[node]:
                    if vals[neighbor] <= val:
                        union(node, neighbor)
            
            # Count nodes in each component with current value
            count = defaultdict(int)
            for node in val_to_nodes[val]:
                count[find(node)] += 1
            
            # Add combinations: C(k, 2) = k*(k-1)/2 for each component
            for k in count.values():
                result += k * (k - 1) // 2
        
        return result

Source