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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Good Paths

Difficulty: Hard

Problem Description

Given a tree with n nodes and an array vals where each node has a value, determine the number of distinct good paths. A good path is defined as a simple path where the starting and ending nodes have the same value, and all intermediate nodes have values less than or equal to that of the starting node.

Key Insights

  • A tree structure is a connected, undirected graph with no cycles.
  • Single nodes are considered valid paths.
  • To form a good path, the maximum value along the path must equal the value of the starting and ending nodes.
  • We can utilize Union-Find (Disjoint Set Union) to efficiently manage connected components and count paths.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting nodes based on their values and processing edges for union operations. Space Complexity: O(n) - for the Union-Find structure and auxiliary data.

Solution

To solve the problem, we can employ a Union-Find (or Disjoint Set Union) approach:

  1. Sort Nodes: Begin by sorting the nodes based on their values. This allows us to process the nodes in non-decreasing order.
  2. Union-Find Structure: Use a Union-Find structure to dynamically connect nodes that can form good paths while processing edges.
  3. Count Good Paths: For each node, after connecting with its neighbors, count how many nodes have the same value and can form good paths. Each group of connected nodes with the same value contributes to the count of good paths.

Code Solutions

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

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

    def union(self, u, v):
        rootU = self.find(u)
        rootV = self.find(v)
        if rootU != rootV:
            if self.size[rootU] < self.size[rootV]:
                rootU, rootV = rootV, rootU
            self.parent[rootV] = rootU
            self.size[rootU] += self.size[rootV]

def numberOfGoodPaths(vals, edges):
    n = len(vals)
    uf = UnionFind(n)
    edges.sort(key=lambda x: max(vals[x[0]], vals[x[1]]))
    
    count = {}
    result = 0

    for i in range(n):
        val = vals[i]
        count[val] = count.get(val, 0) + 1
        result += 1  # Each single node is a good path

        for u, v in edges:
            if vals[u] <= val and vals[v] <= val:
                uf.union(u, v)

        root_count = {}
        for j in range(n):
            if vals[j] == val:
                root = uf.find(j)
                root_count[root] = root_count.get(root, 0) + 1

        for group_size in root_count.values():
            result += (group_size * (group_size - 1)) // 2

    return result
← Back to All Questions