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 II

Number: 3798

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an undirected tree (with n nodes, numbered 0 to n-1) that is rooted at node 0, each edge has a positive length and each node has an associated value. A special path is defined as a downward (from an ancestor to a descendant) path in which every value is distinct except that one value may appear twice. We must return a two-element array: the first element is the maximum total length (i.e. the sum of edge weights) among all special paths, and the second element is the minimum number of nodes used in any special path achieving that maximum length.

Key Insights

  • The tree is rooted, so any downward path is simply a contiguous sequence from some ancestor to a descendant following the unique parent–child relationship.
  • A sliding-window or DFS/backtracking approach can be used along a root-to-leaf path; while traversing the DFS we maintain frequency counts for node values.
  • When adding a node, if its value is new the path remains valid; if it appears once and we haven’t used our “duplicate allowance”, the path remains valid (now using the duplicate spot); if a value would appear more than twice or would introduce a second duplicate, further extension in that path is invalid.
  • Global tracking of the best (maximum weighted length) special path and, in case of ties, the smallest number of nodes is required.
  • DFS with backtracking along the tree suffices because each downward path is uniquely defined by the DFS path.

Space and Time Complexity

Time Complexity: O(n) – Each node is visited once in the DFS and the operations per node are O(1) on average. Space Complexity: O(n) – O(n) recursion stack (in the worst-case when the tree is like a linked list) and O(n) for the frequency hash table.

Solution

We use a DFS traversal from the root while maintaining: • A frequency dictionary (or hashmap) for values along the current path. • A boolean flag (or count) that indicates whether we have already used our duplicate allowance. • The cumulative sum of edge lengths and the count of nodes in the path.

At each DFS step:

  1. For the current node, update the frequency for its value.
  2. If a value is seen for the second time, mark that the duplicate spot is used; if a value count would exceed two then this extension is invalid.
  3. If the path contains at least 2 nodes (since a valid path requires an ancestor and a descendant), update the global maximum path sum. In the event of a tie (equal sum), record the minimum number of nodes encountered.
  4. Recursively call DFS on each valid child (ignoring back edges by passing the parent).
  5. Backtrack by decrementing the frequency for the node when the DFS call returns.

Data Structures/Techniques used are:

  • DFS with backtracking.
  • A frequency dictionary for tracking node values.
  • Global variables to record the current best sum and the corresponding minimum path length.

Code Solutions

Below are code solutions in Python, JavaScript, C++ and Java. Each code snippet is provided with line-by-line comments.

# Python solution using DFS with backtracking

# Import defaultdict for easy frequency count handling
from collections import defaultdict

def longestSpecialPath(edges, nums):
    n = len(nums)
    
    # Build the adjacency list: node -> list of (neighbor, weight)
    tree = [[] for _ in range(n)]
    for u, v, weight in edges:
        tree[u].append((v, weight))
        tree[v].append((u, weight))
    
    # global maximum sum and minimum node count among those paths
    bestPathSum = -1
    bestPathNodes = float('inf')
    
    # DFS function: node, parent, current cumulative sum, count of nodes in path,
    # duplicateUsed is True if we have already encountered a duplicate.
    freq = defaultdict(int)
    
    def dfs(node, parent, currentSum, currentCount, duplicateUsed):
        nonlocal bestPathSum, bestPathNodes
        # Process each neighbor that is not the parent
        for neighbor, weight in tree[node]:
            if neighbor == parent:
                continue
            # Before going, update frequency for neighbor's value
            value = nums[neighbor]
            freq[value] += 1
            newDuplicateUsed = duplicateUsed
            # If this is the 2nd occurrence, we use our allowed duplicate
            if freq[value] == 2:
                newDuplicateUsed = True
            # If frequency goes beyond 2, then the path is invalid, backtrack and skip
            if freq[value] > 2:
                freq[value] -= 1
                continue
            
            newSum = currentSum + weight
            newCount = currentCount + 1
            
            # A valid special path needs at least 2 nodes (ancestor, descendant)
            if newCount >= 2:
                if newSum > bestPathSum:
                    bestPathSum = newSum
                    bestPathNodes = newCount
                elif newSum == bestPathSum and newCount < bestPathNodes:
                    bestPathNodes = newCount
            
            # Continue DFS traversal with neighbor
            dfs(neighbor, node, newSum, newCount, newDuplicateUsed)
            
            # Backtrack: remove neighbor's frequency change before next iteration
            freq[value] -= 1
    
    # Start DFS from the root (node 0)
    freq[nums[0]] = 1  # starting frequency with root's value
    dfs(0, -1, 0, 1, False)
    return [bestPathSum, bestPathNodes]

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