We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Good Paths

Number: 2505

Difficulty: Hard

Paid? No

Companies: TikTok, Google

Problem Description

Given a tree with n nodes (0-indexed) and n - 1 edges, each node has an integer value from the array vals. A good path is defined as a simple path where the starting and ending nodes have the same value and every node on the path (including intermediate nodes) has a value less than or equal to that value. Single nodes count as valid good paths. The task is to count the number of distinct good paths.

Key Insights

  • A single node is trivially a good path.
  • To consider a multi-node path, the maximum value on the path must be at the endpoints.
  • Sorting nodes or edges based on their values can help process connections in a way that respects the “less than or equal to” constraint.
  • Union Find (Disjoint Set Union) can be used to dynamically merge connected components while ensuring that all nodes in the component have a value that is not greater than the current value being processed.
  • When merging components, if two nodes with the same value become connected, the number of good paths increases by the number of ways to choose pairs from nodes with that value within the same connected component.

Space and Time Complexity

Time Complexity: O(n log n)

  • Sorting nodes/edges takes O(n log n)
  • The union-find operations are nearly O(α(n)) per operation, which is effectively constant. Space Complexity: O(n)
  • Space is required for storing the union-find parent and rank arrays as well as auxiliary data structures.

Solution

The approach is as follows:

  1. Create a graph representation from the edges (adjacency list).
  2. Create a list of nodes sorted by their vals.
  3. Use a Union Find (Disjoint Set Union) data structure to join nodes as you iterate through the sorted nodes.
  4. For each node value (processing in ascending order), process the adjacent nodes but only union those edges where the neighbor’s value is less than or equal to the current value.
  5. Maintain a frequency count of nodes with the same value in each connected component. When two nodes with the same value join, it yields additional good paths based on the combination formula (freq * (freq - 1) / 2) for each component.
  6. Sum the good paths from individual nodes (each considered as a good path) plus the additional ones found during unions.

This union by value strategy ensures we only connect nodes that maintain the condition that the maximum value along the path is at the endpoints.

Code Solutions

# Python solution using Union Find (Disjoint Set Union)
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size
        
    def find(self, x):
        # Path compression to flatten the tree
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        # Union by rank to merge smaller tree under larger tree
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        return True

def numberOfGoodPaths(vals, edges):
    n = len(vals)
    # Build adjacency list from edges
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # Group node indices by their value and sort unique values
    val_to_nodes = {}
    for i, val in enumerate(vals):
        val_to_nodes.setdefault(val, []).append(i)
    sorted_vals = sorted(val_to_nodes.keys())
    
    # Each node is a valid good path (single node)
    result = n
    uf = UnionFind(n)
    
    # Additional count: frequency map for union-find representative when adding nodes with current value.
    # visited marks if the node has been processed.
    visited = [False] * n
    
    # Process nodes in the increasing order of values
    for val in sorted_vals:
        for node in val_to_nodes[val]:
            visited[node] = True
            # For each neighbor already processed that meets constraint
            for neighbor in graph[node]:
                if visited[neighbor]:
                    uf.union(node, neighbor)
                    
        # Count the nodes with current value in each connected component (by root)
        count = {}
        for node in val_to_nodes[val]:
            root = uf.find(node)
            count[root] = count.get(root, 0) + 1
        
        # For each component, add additional good paths using pair combinations
        for comp_count in count.values():
            result += (comp_count * (comp_count - 1)) // 2
    
    return result

# Example usage:
print(numberOfGoodPaths([1,3,2,1,3], [[0,1],[0,2],[2,3],[2,4]]))
← Back to All Questions