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

Longest Special Path II

Difficulty: Hard

Problem Description

You are given an undirected tree rooted at node 0, with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [u_i, v_i, length_i] indicates an edge between nodes u_i and v_i with length length_i. You are also given an integer array nums, where nums[i] represents the value at node i.

A special path is defined as a downward path from an ancestor node to a descendant node in which all node values are distinct, except for at most one value that may appear twice.

Return an array result of size 2, where result[0] is the length of the longest special path, and result[1] is the minimum number of nodes in all possible longest special paths.

Key Insights

  • The tree is undirected and rooted at node 0.
  • A special path allows distinct values with one value possibly repeating.
  • We need to traverse the tree and keep track of values seen on the path.
  • Depth-First Search (DFS) is a suitable approach for tree traversal.
  • Use a hash map or set to track counts of node values along the path.
  • Record the length of valid special paths and the number of nodes.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once. Space Complexity: O(n), for storing the visited nodes and their counts.

Solution

To solve the problem, we will use a Depth-First Search (DFS) approach. We will traverse the tree while maintaining a count of the values seen in the current path. When visiting a new node, we will check if its value is already in our count. If it is, we need to ensure it doesn't violate the special path condition. If the path is valid, we will update our maximum path length and node count accordingly. The key data structures used are:

  • A hash map to count occurrences of node values along the current path.
  • A variable to track the current path length and another to track the number of nodes.

Code Solutions

def longest_special_path(edges, nums):
    from collections import defaultdict

    # Build the tree as an adjacency list
    tree = defaultdict(list)
    for u, v, length in edges:
        tree[u].append((v, length))
        tree[v].append((u, length))

    def dfs(node, parent, current_length, current_count):
        nonlocal max_length, min_nodes
        # Add current node's value to the count
        if nums[node] in current_count:
            current_count[nums[node]] += 1
        else:
            current_count[nums[node]] = 1

        # Check path validity and update max_length and min_nodes
        if sum(1 for count in current_count.values() if count > 1) <= 1:
            if current_length > max_length:
                max_length = current_length
                min_nodes = len(current_count)
            elif current_length == max_length:
                min_nodes = min(min_nodes, len(current_count))

        # Explore children
        for neighbor, length in tree[node]:
            if neighbor != parent:  # Avoid going back to the parent
                dfs(neighbor, node, current_length + length, current_count)

        # Backtrack: remove current node's value from the count
        current_count[nums[node]] -= 1
        if current_count[nums[node]] == 0:
            del current_count[nums[node]]

    max_length = 0
    min_nodes = float('inf')
    dfs(0, -1, 0, {})
    
    return [max_length, min_nodes]

# Example usage
edges1 = [[0,1,1],[1,2,3],[1,3,1],[2,4,6],[4,7,2],[3,5,2],[3,6,5],[6,8,3]]
nums1 = [1,1,0,3,1,2,1,1,0]
print(longest_special_path(edges1, nums1))  # Output: [9, 3]
← Back to All Questions