Longest Special Path
HardPrompt
You are given an undirected tree rooted at node 0 with n nodes numbered from 0 to n - 1, 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 such that all the values of the nodes in that path are unique.
Note that a path may start and end at the same node.
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,2],[1,2,3],[1,3,5],[1,4,4],[2,5,6]], nums = [2,1,2,1,3,1]
Output: [6,2]
Explanation:
In the image below, nodes are colored by their corresponding values in nums
The longest special paths are 2 -> 5 and 0 -> 1 -> 4, both having a length of 6. The minimum number of nodes across all longest special paths is 2.
Example 2:
Input: edges = [[1,0,8]], nums = [2,2]
Output: [0,1]
Explanation:
The longest special paths are 0 and 1, both having a length of 0. The minimum number of nodes across all longest special paths is 1.
Constraints:
2 <= n <= 5 * 104edges.length == n - 1edges[i].length == 30 <= ui, vi < n1 <= lengthi <= 103nums.length == n0 <= nums[i] <= 5 * 104- The input is generated such that
edgesrepresents a valid tree.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a straightforward brute-force method. It considers every node in the tree as a potential starting point for a special path. From each potential start node, it performs a Depth-First Search (DFS) to explore all possible downward paths. During the DFS, it maintains a set of visited node values to ensure the path's 'special' property (unique values). It keeps track of the longest special path found so far and the minimum number of nodes for that length.
Algorithm
- Build Adjacency List: First, convert the
edgesarray into an adjacency list representation of the tree, where each entry stores the neighbor and the edge length. Since the problem defines a rooted tree structure with downward paths, we also establish parent-child relationships, for instance, by performing a preliminary Breadth-First Search (BFS) or Depth-First Search (DFS) starting from the root (node 0). - Iterate Through All Start Nodes: The main idea is to check every possible downward path. A downward path can start at any node in the tree. Therefore, we iterate through each node
sfrom0ton-1, treating it as a potential starting node for a special path. - Depth-First Search for Paths: For each starting node
s, we perform a DFS to explore all downward paths originating from it. The DFS function, sayfindPaths(u, currentLength, numNodes, visitedValues), will traverse the subtree rooted atu. - Path Validation and State Update:
u: The current node in the traversal.currentLength: The sum of edge lengths fromstou's parent.numNodes: The number of nodes on the path fromstou's parent.visitedValues: AHashSetto keep track of thenumsvalues of nodes on the current path froms.
- DFS Logic:
- Inside the
findPathsfunction for nodeu, first check ifnums[u]is already invisitedValues. If it is, this path is no longer special, so we terminate this branch of the search. - If
nums[u]is unique, we have a valid special path ending atu. We compare its length (currentLength) and node count (numNodes) with the globalmaxLengthandminNodes, updating them if we've found a new longest path or one with the same length but fewer nodes. - To explore further down, add
nums[u]tovisitedValues. - Recursively call
findPathsfor all childrenvofu, updating the length and node count accordingly:findPaths(v, currentLength + edge_length(u,v), numNodes + 1, visitedValues). - After the recursive calls for all children return (i.e., after exploring all paths through
u), backtrack by removingnums[u]fromvisitedValuesto ensure correctness for other paths in the tree.
- Inside the
- Return Result: After iterating through all possible starting nodes,
maxLengthandminNodeswill hold the final answer.
Walkthrough
The algorithm begins by constructing a directed graph or tree structure from the input edges, typically using an adjacency list, to easily traverse from parent to child. Then, it iterates through every node i from 0 to n-1, treating each as the root of a potential longest special path.
For each starting node s, a recursive DFS function is invoked. This function explores all paths downwards from s. It takes the current node, the path's length so far, the number of nodes, and a set of the nums values encountered on the path as arguments. At each node u in the traversal, it checks if nums[u] is already in the set of values. If it is, the path is no longer special, and the recursion for this branch stops. Otherwise, it's a valid special path, and we update our global maximum length and corresponding minimum nodes. The process continues by recursively calling the DFS for all children of u. Backtracking is used to remove nums[u] from the set when returning from the recursion, allowing other paths to be evaluated correctly.
class Solution { private List<int[]>[] adj; private int[] nums; private long maxLength = 0; private int minNodes = 1; public int[] longestSpecialPath(int[][] edges, int[] nums) { int n = nums.length; this.nums = nums; this.adj = new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); } for (int[] edge : edges) { adj[edge[0]].add(new int[]{edge[1], edge[2]}); adj[edge[1]].add(new int[]{edge[0], edge[2]}); } // Create a directed tree for downward traversal List<int[]>[] directedAdj = new ArrayList[n]; for (int i = 0; i < n; i++) { directedAdj[i] = new ArrayList<>(); } boolean[] visited = new boolean[n]; Queue<Integer> q = new LinkedList<>(); q.add(0); visited[0] = true; while (!q.isEmpty()) { int u = q.poll(); for (int[] edge : adj[u]) { int v = edge[0]; if (!visited[v]) { visited[v] = true; directedAdj[u].add(edge); q.add(v); } } } this.adj = directedAdj; for (int i = 0; i < n; i++) { dfs(i, 0, 1, new HashSet<>()); } return new int[]{(int)maxLength, minNodes}; } private void dfs(int u, long currentLength, int numNodes, Set<Integer> visitedValues) { if (visitedValues.contains(nums[u])) { return; } if (currentLength > maxLength) { maxLength = currentLength; minNodes = numNodes; } else if (currentLength == maxLength) { minNodes = Math.min(minNodes, numNodes); } visitedValues.add(nums[u]); for (int[] edge : adj[u]) { int v = edge[0]; int length = edge[1]; dfs(v, currentLength + length, numNodes + 1, visitedValues); } visitedValues.remove(nums[u]); }}Complexity
Time
O(N^2 * D) - In the worst case, we start a DFS from each of the N nodes. Each DFS can traverse a subtree of size up to N. For each node in the path, we do a constant time set operation. The depth D of the recursion can be up to N. A loose upper bound is O(N * N!) but a tighter one is closer to O(N^2 * D), where D is the average depth, making it very slow.
Space
O(N) - The space complexity is dominated by the recursion stack depth of the DFS, which can be up to O(N) in the worst case (a skewed tree or line graph). The `visitedValues` set can also store up to O(N) values.
Trade-offs
Pros
Conceptually simple and easy to follow.
Correctly solves the problem for small inputs.
Cons
Extremely inefficient due to redundant computations. Many paths are explored multiple times.
The time complexity is prohibitive for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
A highly efficient solution can be achieved using a form of Dynamic Programming on trees, optimized with the DSU on Trees (also known as Sack) technique. This approach avoids the redundant computations of the brute-force method by processing the tree in a post-order traversal and cleverly merging results from subtrees.
The core of this method is a DFS function that, for each node u, computes a map of the longest special paths starting at u. To handle the uniqueness constraint efficiently, we use an auxiliary data structure—a map of stacks (valToNodeStack). This structure helps to quickly identify if extending a path from a child with its parent u would violate the uniqueness constraint by introducing a duplicate nums[u] value. The DSU on Trees optimization ensures that we only do full computations for smaller subtrees (light children) and merge their results into the already computed results of the largest subtree (heavy child), bringing the overall complexity down significantly.
Algorithm
- Preprocessing:
- Build an adjacency list for the tree.
- Perform a single DFS from the root (0) to compute subtree sizes, parent pointers, and
tin/touttimes for each node.tin[u]andtout[u]are the entry and exit times of nodeuin the DFS traversal, which allow for O(1) ancestor checks (is_ancestor(u, v)is true iftin[u] <= tin[v]andtout[u] >= tout[v]).
- DSU on Trees (Sack) Framework: We use a post-order traversal. The core idea is to compute results for smaller subtrees (light children) and merge them into the result of the largest subtree (heavy child) to avoid recomputing for the heavy path.
- State Representation: For each node
u, we compute a map,M_u: end_val -> {length, nodes, end_node_id}. This map stores information about the longest special paths that start atuand end at a descendantd(withnums[d] = end_val). - Conflict Detection: The main challenge is checking if a path can be extended. When at node
u, to extend a path from a childc, we must ensurenums[u]is not present on the child's path. We use a global map of stacks,valToNodeStack, wherevalToNodeStack[v]stores a stack of nodes on the current DFS path from the root that have the valuev. The top of the stackvalToNodeStack[nums[u]]gives us the highest ancestor of the current nodeuthat has the same value. This ancestor is a potential 'blocker'. - Recursive DFS with Sack (
dfs_sack):- Find Heavy Child: For the current node
u, identify its heavy child (the one with the largest subtree). - Recurse on Light Children: Call
dfs_sackfor all light children. After each call, clear the data computed for that light child to save memory. - Recurse on Heavy Child: Call
dfs_sackfor the heavy child, but instruct it to keep its computed map. This map becomes the base foru's map. - Merge Step:
a. Update Heavy Child's Paths: Iterate through the map inherited from the heavy child
hc. For each pathhc -> ... -> d, check if it's blocked bynums[u]. A path is blocked if the highest ancestor with valuenums[u](found usingvalToNodeStack) is a descendant ofhc. If not blocked, update the path's length and node count by prepending the edgeu -> hc. b. Add Path foru: Add the path consisting of only nodeu(length 0, 1 node) to the map. c. Merge Light Children's Paths: For each light childlc, re-run the DFS to get its map. Iterate through this map and merge valid, unblocked paths intou's map. - Update Global Answer: After every modification to
u's map, update the globalmaxLengthandminNodes. - Manage State: The
valToNodeStackis updated in a preorder/postorder fashion within the main DFS traversal to correctly reflect the ancestor chain.
- Find Heavy Child: For the current node
Walkthrough
This advanced approach combines several techniques. First, we preprocess the tree to determine subtree sizes and tin/tout times for O(1) ancestor checks. The main algorithm is a recursive DFS that implements the DSU on Trees (Sack) heuristic.
The state passed up during the post-order traversal from a node u is a map. This map, M_u, keys on a node value v and stores a tuple {length, nodes, end_node} representing the longest special path that starts at u and ends at a descendant end_node having nums[end_node] == v.
At a node u, the algorithm first recursively calls itself on all its 'light' children (children with smaller subtrees) and discards their returned maps. Then, it calls itself on its 'heavy' child and reuses its map. This map is then updated: for each path starting at the heavy child, we check if it can be extended by u. This check is the crucial part. We use a global map of stacks, valToNodeStack, where valToNodeStack[v] contains all nodes on the current path from the root with value v. If the highest node on this stack is in the heavy child's subtree, the path is blocked. Otherwise, we extend the path, update its length/nodes, and update the global answer. We then add the path for u itself. Finally, we iterate through the light children again, compute their maps, and merge their valid paths into u's map. This merging of smaller maps into a larger one is what gives DSU on Trees its efficiency.
class Solution { private List<int[]>[] adj; private int[] nums; private int[] subtreeSize; private int[] tin, tout; private int timer; private long maxLength = 0; private int minNodes = 1; private Map<Integer, Deque<Integer>> valToNodeStack = new HashMap<>(); private Map<Integer, PathInfo>[] maps; static class PathInfo { long length; int nodes; int endNode; PathInfo(long length, int nodes, int endNode) { this.length = length; this.nodes = nodes; this.endNode = endNode; } } public int[] longestSpecialPath(int[][] edges, int[] nums) { int n = nums.length; this.nums = nums; adj = new ArrayList[n]; for (int i = 0; i < n; i++) adj[i] = new ArrayList<>(); for (int[] edge : edges) { adj[edge[0]].add(new int[]{edge[1], edge[2]}); adj[edge[1]].add(new int[]{edge[0], edge[2]}); } subtreeSize = new int[n]; tin = new int[n]; tout = new int[n]; maps = new HashMap[n]; // Pre-computation DFS dfs_size(0, -1); // Main DFS with Sack dfs_sack(0, -1); return new int[]{(int)maxLength, minNodes}; } private void dfs_size(int u, int p) { tin[u] = timer++; subtreeSize[u] = 1; List<int[]> children = new ArrayList<>(); for (int[] edge : adj[u]) { int v = edge[0]; if (v != p) { children.add(edge); dfs_size(v, u); subtreeSize[u] += subtreeSize[v]; } } adj[u] = children; tout[u] = timer++; } private boolean isAncestor(int u, int v) { if (u == -1 || v == -1) return false; return tin[u] <= tin[v] && tout[u] >= tout[v]; } private void updateGlobal(long len, int nodes) { if (len > maxLength) { maxLength = len; minNodes = nodes; } else if (len == maxLength) { minNodes = Math.min(minNodes, nodes); } } private void dfs_sack(int u, int p) { valToNodeStack.computeIfAbsent(nums[u], k -> new ArrayDeque<>()).push(u); int heavyChild = -1, maxSubtree = -1; for (int[] edge : adj[u]) { int v = edge[0]; if (subtreeSize[v] > maxSubtree) { maxSubtree = subtreeSize[v]; heavyChild = v; } } for (int[] edge : adj[u]) { int v = edge[0]; if (v != heavyChild) { dfs_sack(v, u); } } if (heavyChild != -1) { dfs_sack(heavyChild, u); maps[u] = maps[heavyChild]; } else { maps[u] = new HashMap<>(); } // Merge logic // Process paths from heavy child int u_val = nums[u]; int blockerNode = valToNodeStack.get(u_val).size() > 1 ? valToNodeStack.get(u_val).peek() : -1; if (valToNodeStack.get(u_val).size() > 1) { valToNodeStack.get(u_val).pop(); blockerNode = valToNodeStack.get(u_val).peek(); valToNodeStack.get(u_val).push(u); } List<Integer> toRemove = new ArrayList<>(); for (Map.Entry<Integer, PathInfo> entry : maps[u].entrySet()) { PathInfo pi = entry.getValue(); if (isAncestor(heavyChild, blockerNode) && isAncestor(blockerNode, pi.endNode)) { toRemove.add(entry.getKey()); } else { pi.length += getEdgeLength(u, heavyChild); pi.nodes++; updateGlobal(pi.length, pi.nodes); } } for (int key : toRemove) maps[u].remove(key); // Add path for u itself PathInfo selfPath = new PathInfo(0, 1, u); if (!maps[u].containsKey(u_val) || maps[u].get(u_val).length < selfPath.length) { maps[u].put(u_val, selfPath); updateGlobal(0, 1); } // Merge light children for (int[] edge : adj[u]) { int v = edge[0]; if (v != heavyChild) { for (Map.Entry<Integer, PathInfo> entry : maps[v].entrySet()) { PathInfo pi = entry.getValue(); if (!(isAncestor(v, blockerNode) && isAncestor(blockerNode, pi.endNode))) { long newLen = pi.length + edge[1]; int newNodes = pi.nodes + 1; if (!maps[u].containsKey(entry.getKey()) || maps[u].get(entry.getKey()).length < newLen) { maps[u].put(entry.getKey(), new PathInfo(newLen, newNodes, pi.endNode)); } updateGlobal(newLen, newNodes); } } } } valToNodeStack.get(nums[u]).pop(); } private int getEdgeLength(int u, int v) { for (int[] edge : adj[u]) { if (edge[0] == v) return edge[1]; } return 0; // Should not happen }}Complexity
Time
O(N log N) - Preprocessing (DFS for sizes, tin/tout) takes O(N). The main `dfs_sack` function processes each node. Due to the DSU on Trees heuristic, each node's information is merged into its parent's map. A node is part of a light child's subtree O(log N) times. Each merge operation takes time proportional to the size of the light child's map. The total time complexity for the Sack part is O(N log N).
Space
O(N) - The space complexity is determined by the adjacency list, recursion stack, and the maps used in the Sack algorithm. The total size of all maps at any point in the recursion is bounded by O(N). The `valToNodeStack` also stores at most O(N) elements in total across all stacks.
Trade-offs
Pros
Highly efficient and passes within the time limits for large inputs.
Solves the problem in a single pass over the tree after preprocessing.
Cons
Significantly more complex to understand and implement correctly than the brute-force approach.
The logic for merging maps and checking for blockers requires careful handling of pointers and data structures.
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.