3486. Longest Special Path II LeetCode Solution

Last updated: March 17, 2025

In this guide, you will get 3486. Longest Special Path II LeetCode Solution with the best time and space complexity. The solution to Longest Special Path II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Longest Special Path II solution in C++
Longest Special Path II solution in Java
Longest Special Path II solution in Python
Additional Resources

3486. Longest Special Path II LeetCode Solution image

Problem Statement of Longest Special Path II

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] = [ui, vi, lengthi] indicates an edge between nodes ui and vi with length lengthi. 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.

Example 1:

Input: 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]
Output: [9,3]
Explanation:
In the image below, nodes are colored by their corresponding values in nums.

The longest special paths are 1 -> 2 -> 4 and 1 -> 3 -> 6 -> 8, both having a length of 9. The minimum number of nodes across all longest special paths is 3.

Example 2:

Input: edges = [[1,0,3],[0,2,4],[0,3,5]], nums = [1,1,0,2]
Output: [5,2]
Explanation:

The longest path is 0 -> 3 consisting of 2 nodes with a length of 5.

Constraints:

2 <= n <= 5 * 104
edges.length == n – 1
edges[i].length == 3
0 <= ui, vi < n
1 <= lengthi <= 103
nums.length == n
0 <= nums[i] <= 5 * 104
The input is generated such that edges represents a valid tree.

Complexity Analysis

Time Complexity: O(|V| + |E|)
Space Complexity: O(|V| + |E|)

3486. Longest Special Path II LeetCode Solution in C++

class Solution {
 public:
  vector<int> longestSpecialPath(vector<vector<int>>& edges,
                                 vector<int>& nums) {
    vector<vector<pair<int, int>>> graph(nums.size());

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      const int w = edge[2];
      graph[u].emplace_back(v, w);
      graph[v].emplace_back(u, w);
    }

    int maxLength = 0;
    int minNodes = 1;
    dfs(graph, 0, -1, /*leftBoundary=*/{0, 0}, /*prefix=*/{0},
        /*lastSeenDepth=*/{}, nums, maxLength, minNodes);
    return {maxLength, minNodes};
  }

 private:
  void dfs(const vector<vector<pair<int, int>>>& graph, int u, int prev,
           vector<int> leftBoundary, vector<int>&& prefix,
           unordered_map<int, int>&& lastSeenDepth, const vector<int>& nums,
           int& maxLength, int& minNodes) {
    const int prevDepth = lastSeenDepth[nums[u]];
    lastSeenDepth[nums[u]] = prefix.size();

    if (prevDepth != 0) {
      leftBoundary.push_back(prevDepth);
      ranges::sort(leftBoundary);
      leftBoundary = {leftBoundary[leftBoundary.size() - 2],
                      leftBoundary.back()};
    }

    const int length = prefix.back() - prefix[leftBoundary[0]];
    const int nodes = prefix.size() - leftBoundary[0];
    if (length > maxLength || (length == maxLength && nodes < minNodes)) {
      maxLength = length;
      minNodes = nodes;
    }

    for (const auto& [v, w] : graph[u]) {
      if (v == prev)
        continue;
      prefix.push_back(prefix.back() + w);
      dfs(graph, v, u, leftBoundary, std::move(prefix),
          std::move(lastSeenDepth), nums, maxLength, minNodes);
      prefix.pop_back();
    }

    lastSeenDepth[nums[u]] = prevDepth;
  }
};
/* code provided by PROGIEZ */

3486. Longest Special Path II LeetCode Solution in Java

class Solution {
  public int[] longestSpecialPath(int[][] edges, int[] nums) {
    List<Pair<Integer, Integer>>[] graph = new List[nums.length];

    for (int i = 0; i < nums.length; ++i)
      graph[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      final int w = edge[2];
      graph[u].add(new Pair<>(v, w));
      graph[v].add(new Pair<>(u, w));
    }

    int[] ans = new int[2];
    ans[0] = 0; // maxLength
    ans[1] = 1; // minNodes
    dfs(graph, 0, -1, /*leftBoundary=*/List.of(0, 0),
        /*prefix=*/new ArrayList<>(List.of(0)),
        /*lastSeenDepth=*/new HashMap<>(), nums, ans);
    return ans;
  }

  private void dfs(List<Pair<Integer, Integer>>[] graph, int u, int prev,
                   List<Integer> leftBoundary, List<Integer> prefix,
                   Map<Integer, Integer> lastSeenDepth, int[] nums, int[] ans) {
    final int prevDepth = lastSeenDepth.getOrDefault(nums[u], 0);
    lastSeenDepth.put(nums[u], prefix.size());

    if (prevDepth != 0) {
      leftBoundary.add(prevDepth);
      Collections.sort(leftBoundary);
      leftBoundary = List.of(leftBoundary.get(leftBoundary.size() - 2),
                             leftBoundary.get(leftBoundary.size() - 1));
    }

    final int length = prefix.get(prefix.size() - 1) - prefix.get(leftBoundary.get(0));
    final int nodes = prefix.size() - leftBoundary.get(0);
    if (length > ans[0] || (length == ans[0] && nodes < ans[1])) {
      ans[0] = length;
      ans[1] = nodes;
    }

    for (Pair<Integer, Integer> pair : graph[u]) {
      final int v = pair.getKey();
      final int w = pair.getValue();
      if (v == prev)
        continue;
      prefix.add(prefix.get(prefix.size() - 1) + w);
      dfs(graph, v, u, new ArrayList<>(leftBoundary), prefix, lastSeenDepth, nums, ans);
      prefix.remove(prefix.size() - 1);
    }

    lastSeenDepth.put(nums[u], prevDepth);
  }
}
// code provided by PROGIEZ

3486. Longest Special Path II LeetCode Solution in Python

class Solution:
  # Similar to 3425. Longest Special Path
  def longestSpecialPath(
      self,
      edges: list[list[int]],
      nums: list[int]
  ) -> list[int]:
    maxLength = 0
    minNodes = 1
    graph = [[] for _ in range(len(nums))]

    for u, v, w in edges:
      graph[u].append((v, w))
      graph[v].append((u, w))

    prefix = [0]
    lastSeenDepth = {}

    def dfs(
        u: int,
        prev: int,
        leftBoundary: list[int],
    ) -> None:
      nonlocal maxLength, minNodes
      prevDepth = lastSeenDepth.get(nums[u], 0)
      lastSeenDepth[nums[u]] = len(prefix)

      if prevDepth != 0:
        leftBoundary = sorted(leftBoundary + [prevDepth])[-2:]

      length = prefix[-1] - prefix[leftBoundary[0]]
      nodes = len(prefix) - leftBoundary[0]
      if length > maxLength or (length == maxLength and nodes < minNodes):
        maxLength = length
        minNodes = nodes

      for v, w in graph[u]:
        if v == prev:
          continue
        prefix.append(prefix[-1] + w)
        dfs(v, u, leftBoundary)
        prefix.pop()

      lastSeenDepth[nums[u]] = prevDepth

    dfs(0, -1, leftBoundary=[0, 0])
    return [maxLength, minNodes]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents