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

Longest Special Path

Number: 3687

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a tree (an undirected acyclic connected graph) with n nodes rooted at node 0, where each edge has an associated length and each node carries an integer value from the given array nums, we need to find a downward “special path”. A special path is a path from an ancestor to a descendant (possibly just a single node) such that all node values in the path are unique. We must return a two-element array: the first element is the maximum total edge length among all special paths, and the second is the minimum number of nodes of any special path that achieves that maximum length.

Key Insights

  • The tree is naturally rooted at node 0; although input edges are undirected, they form a tree.
  • A DFS (Depth-first search) is ideal to traverse downward from the root while keeping track of unique node values.
  • Backtracking is used to add and remove a node’s value as we traverse and unwind the recursive calls.
  • For every valid path (when visiting a node), update a global maximum length and compare the number of nodes so far if a maximum path length tie occurs.
  • A special path may consist of a single node, which has zero edge length.

Space and Time Complexity

Time Complexity: O(n) – Every node is visited once along each unique path branch. Space Complexity: O(n) – In worst-case, the recursion stack and auxiliary set may hold up to n nodes.

Solution

We use Depth-first Search (DFS) to traverse the tree starting at the root (node 0). When moving from an ancestor to a descendant, we maintain a set (or dictionary) to track used values ensuring each node’s value is unique in our current path. For each node, we update the best (longest) path length and record the minimum number of nodes needed if the same maximum length is reached. After processing a node’s children, we backtrack by removing the node’s value from our set ensuring that each branch is processed correctly. This way, we are exploring all possible downward paths and tracking the desired metrics.

Code Solutions

# Python solution with detailed comments

from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def longestSpecialPath(edges, nums):
    # Build an adjacency list from the edges list
    # Each entry: node -> list of tuples (neighbor, edge_length)
    graph = defaultdict(list)
    for u, v, length in edges:
        graph[u].append((v, length))
        graph[v].append((u, length))
    
    # Global variables to store best (max) path length and minimal node count among such paths.
    best = [0, float('inf')]  # best[0] = max total edge length, best[1] = minimal nodes count
    
    def dfs(node, parent, current_length, node_count, visited):
        # Update global best if current path qualifies.
        if current_length > best[0]:
            best[0] = current_length
            best[1] = node_count
        elif current_length == best[0]:
            best[1] = min(best[1], node_count)
        
        # Traverse children (i.e., neighbors except the parent)
        for neighbor, edge_len in graph[node]:
            if neighbor == parent:
                continue
            # Only continue if the neighbor's value is not already in the path
            if nums[neighbor] in visited:
                continue
            # Add the neighbor's value into the visited set
            visited.add(nums[neighbor])
            dfs(neighbor, node, current_length + edge_len, node_count + 1, visited)
            # Backtracking: remove neighbor's value from visited set after finishing DFS for that branch.
            visited.remove(nums[neighbor])
    
    # Start DFS from root (node 0) with its value in the visited set.
    visited = set([nums[0]])
    dfs(0, -1, 0, 1, visited)
    
    return best

# Example usage:
# edges = [[0,1,2],[1,2,3],[1,3,5],[1,4,4],[2,5,6]]
# nums = [2,1,2,1,3,1]
# print(longestSpecialPath(edges, nums))  # Expected Output: [6,2]
← Back to All Questions