Longest Special Path II

Hard

#3099Time: O(N^2) in the worst case. For each node, we iterate through its children's maps. In a path graph, this leads to a quadratic number of operations.Space: O(N^2) in the worst case. For a path graph, the map returned by a node can contain entries for all nodes in its subtree.

Patterns

Prefix Sum

Algorithms

Depth-First Search

Data structures

Array Hash Table Tree

Prompt

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.

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 * 10⁴
edges.length == n - 1
edges[i].length == 3
0 <= u_i, v_i < n
1 <= length_i <= 10³
nums.length == n
0 <= nums[i] <= 5 * 10⁴
The input is generated such that edges represents a valid tree.

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward dynamic programming approach on the tree can be used. We can perform a post-order traversal (DFS) from the root. For each node, we compute information about the paths starting at that node and going downwards. This information is then passed up to its parent to compute information for longer paths.

Algorithm

Represent the tree using an adjacency list where each entry stores the neighbor and the edge length.
Define a recursive DFS function, say dfs(u, p), that traverses the tree in a post-order fashion. This function will compute and return information about paths starting at node u and descending into its subtree.
The information returned by dfs(u, p) will be a map, let's call it pathMap. The keys of this map are node values, and the values are pairs (length, nodes) representing a path. Specifically, pathMap[val] will store the (length, nodes) of the longest downward path with distinct node values starting at u that contains the value val.
Inside dfs(u, p): a. Initialize a map for the current node u, map_u. Add the path consisting of only u itself: map_u.put(nums[u], (0L, 1)). Update the global answer with this path. b. For each child v of u, recursively call dfs(v, u) to get its map, map_v. c. Merge map_v into map_u. For each entry (val, path) in map_v: i. Create a new path by prepending u. The new path has length path.length + edge_length(u, v) and path.nodes + 1 nodes. ii. If val == nums[u], this new path has a repeated value (nums[u]). This is a valid special path. Update the global answer with this new path's properties. iii. If val != nums[u], the new path is still a distinct-valued path. Update the global answer. Then, merge this new path's information into map_u. For every value x on this new path (which are nums[u] and the values from the path from v), we should update map_u[x]. Since we don't store all values on the path, we can only update map_u[val] and map_u[nums[u]] with the new path, taking the maximum if an entry already exists.
The global answer, a pair (maxLength, minNodes), is updated whenever a valid special path (either distinct-valued or with one repeat) is found or created. The update logic is: if the new path is longer, replace the answer. If it's equally long, take the one with fewer nodes.

Walkthrough

The core of this approach is a DFS function that, for each node u, calculates properties of paths starting at u. The function returns a map where keys are node values and values are pairs of (length, nodes). map[value] stores the longest distinct-valued path starting at u that contains value.

When traversing, for a node u, we first recursively call the DFS on all its children. Each call for a child v returns a map map_v. We then merge map_v into u's map, map_u.

When merging, a path from v is extended to u. If nums[u] is the same as a value on the path from v, a special path with a repeated value is formed. We update our global answer. Otherwise, a new, longer distinct-valued path is formed. We update the global answer and merge this new path's information into map_u.

The main drawback is the merging process. In the worst case (e.g., a path graph), a node's map might need to incorporate a large map from its child, leading to O(N^2) complexity.

1class Solution {2    // Using a custom Pair class for {length, nodes}3    static class Pair {4        long len;5        int nodes;6        Pair(long len, int nodes) {7            this.len = len;8            this.nodes = nodes;9        }10    }11 12    long maxLength = -1;13    int minNodes = -1;14 15    public int[] longestSpecialPath(int[][] edges, int[] nums) {16        int n = nums.length;17        List<List<int[]>> adj = new ArrayList<>();18        for (int i = 0; i < n; i++) {19            adj.add(new ArrayList<>());20        }21        for (int[] edge : edges) {22            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});23            adj.get(edge[1]).add(new int[]{edge[0], edge[2]});24        }25 26        List<List<int[]>> children = new ArrayList<>();27        for (int i = 0; i < n; i++) {28            children.add(new ArrayList<>());29        }30        // Build a directed tree from the undirected graph31        Queue<Integer> q = new LinkedList<>();32        q.offer(0);33        boolean[] visited = new boolean[n];34        visited[0] = true;35        while (!q.isEmpty()) {36            int u = q.poll();37            for (int[] edge : adj.get(u)) {38                int v = edge[0];39                if (!visited[v]) {40                    visited[v] = true;41                    children.get(u).add(edge);42                    q.offer(v);43                }44            }45        }46 47        dfs(0, children, nums);48        return new int[]{(int)maxLength, minNodes};49    }50 51    private Map<Integer, Pair> dfs(int u, List<List<int[]>> children, int[] nums) {52        Map<Integer, Pair> mapU = new HashMap<>();53        mapU.put(nums[u], new Pair(0, 1));54        updateGlobal(0, 1);55 56        for (int[] edge : children.get(u)) {57            int v = edge[0];58            int length = edge[1];59            Map<Integer, Pair> mapV = dfs(v, children, nums);60 61            for (Map.Entry<Integer, Pair> entry : mapV.entrySet()) {62                int val = entry.getKey();63                Pair pathV = entry.getValue();64                long newLen = pathV.len + length;65                int newNodes = pathV.nodes + 1;66 67                if (val == nums[u]) { // Path with one repeat68                    updateGlobal(newLen, newNodes);69                } else { // Distinct path70                    updateGlobal(newLen, newNodes);71                    // Merge into mapU72                    if (!mapU.containsKey(val) || isBetter(newLen, newNodes, mapU.get(val))) {73                        mapU.put(val, new Pair(newLen, newNodes));74                    }75                }76            }77        }78        return mapU;79    }80 81    private void updateGlobal(long len, int nodes) {82        if (len > maxLength) {83            maxLength = len;84            minNodes = nodes;85        } else if (len == maxLength) {86            minNodes = Math.min(minNodes, nodes);87        }88    }89 90    private boolean isBetter(long len1, int nodes1, Pair p2) {91        if (len1 > p2.len) return true;92        if (len1 == p2.len && nodes1 < p2.nodes) return true;93        return false;94    }95}

Complexity

Time

O(N^2) in the worst case. For each node, we iterate through its children's maps. In a path graph, this leads to a quadratic number of operations.

Space

O(N^2) in the worst case. For a path graph, the map returned by a node can contain entries for all nodes in its subtree.

Trade-offs

Pros

Conceptually simpler than more optimized solutions.
Correct for all cases, just not efficient enough for large constraints.

Cons

The time complexity is high for certain tree structures like a line graph (or path graph), where the size of the map returned can grow up to O(N) at each level.
The space complexity is also high in the worst-case, as the maps can become large.

This approach optimizes the simple Tree DP by using a technique known as Sack, or DSU on trees. The main bottleneck in the previous approach was the repeated construction and merging of path information maps. Sack optimization reduces this redundant work by applying a heavy-light decomposition strategy to the tree traversal.

Algorithm

Preprocessing: Perform a preliminary DFS from the root (node 0) to build a directed child-only adjacency list and to compute the subtree size for each node.
Heavy-Light Decomposition Idea: In the main DFS traversal, for each node u, identify its "heavy child" - the child with the largest subtree. All other children are "light children".
Main DFS (dfs_sack): This function will solve the problem for the subtree at u and return a map representing paths, similar to the simple DP approach. a. Recursively call dfs_sack for all light children of u. After each call returns, we clear the map data generated for that light subtree. The global answer will have been updated for paths entirely within that light subtree. b. Recursively call dfs_sack for the heavy child hc. Crucially, we keep the map returned from this call. c. This inherited map from hc contains paths starting at hc. We transform it into a map for paths starting at u (by adding the edge (u, hc) length and incrementing node counts). d. While transforming, if we encounter a path that now creates a repeat with nums[u], we've found a special path. We update the global answer. These entries are then conceptually removed from being 'distinct' paths. e. Add the path of node u itself ((0, 1)) to the map and update the global answer. f. Now, merge the light children's information. For each light child lc, we do another DFS on its subtree to collect its path map. Then, we iterate through this temporary map and merge its information into the main map (from the heavy child), updating the global answer for any new special paths (repeated or distinct) that are formed.
Sack Optimization: The key is that we only do a full traversal and map creation for light subtrees. The map from the heavy child is reused. Since a path from the root to any node crosses at most O(log N) light edges, each node's information is merged at most O(log N) times. This reduces the overall complexity.

Walkthrough

The algorithm is a sophisticated form of tree DP. We first determine the size of each node's subtree. This allows us to distinguish between a node's 'heavy' child (the one with the largest subtree) and its 'light' children.

The main DFS traversal processes nodes in a specific order to minimize work. For a node u, it first recursively visits all light children, computes the answer for their subtrees, and then discards their path information. Then, it visits the heavy child and reuses its computed path map. This map is updated to reflect paths starting from u through the heavy child.

Finally, it revisits the light children's subtrees, computes their path maps again, and merges this information into the main map inherited from the heavy child. During all these steps, we check for the two types of special paths:

Distinct-valued paths: Any path in our map is a distinct-valued path. We update the global answer whenever we create or lengthen one.
One-repeat paths: These are formed when we extend a path from a child v with its parent u, and nums[u] is already present on the path from v. We detect this when the value nums[u] is a key in the child's path map.

The Sack technique ensures that information from smaller subtrees is merged into information from larger ones, limiting the total number of map operations across the entire traversal to O(N log N).

1class Solution {2    static class Pair {3        long len;4        int nodes;5        Pair(long len, int nodes) {6            this.len = len;7            this.nodes = nodes;8        }9    }10 11    long maxLength = -1;12    int minNodes = -1;13    List<List<int[]>> children;14    int[] subtreeSize;15    int[] nums;16 17    public int[] longestSpecialPath(int[][] edges, int[] nums) {18        int n = nums.length;19        this.nums = nums;20        List<List<int[]>> adj = new ArrayList<>();21        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());22        for (int[] edge : edges) {23            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});24            adj.get(edge[1]).add(new int[]{edge[0], edge[2]});25        }26 27        children = new ArrayList<>();28        for (int i = 0; i < n; i++) children.add(new ArrayList<>());29        subtreeSize = new int[n];30        buildTreeAndSizes(0, -1, adj);31 32        dfsSack(0);33        return new int[]{(int)maxLength, minNodes};34    }35 36    private void buildTreeAndSizes(int u, int p, List<List<int[]>> adj) {37        subtreeSize[u] = 1;38        for (int[] edge : adj.get(u)) {39            int v = edge[0];40            if (v == p) continue;41            children.get(u).add(edge);42            buildTreeAndSizes(v, u, adj);43            subtreeSize[u] += subtreeSize[v];44        }45    }46 47    private Map<Integer, Pair> dfsSack(int u) {48        int heavyChild = -1, maxSubtree = -1, heavyChildLen = 0;49        for (int[] edge : children.get(u)) {50            int v = edge[0];51            if (subtreeSize[v] > maxSubtree) {52                maxSubtree = subtreeSize[v];53                heavyChild = v;54                heavyChildLen = edge[1];55            }56        }57 58        Map<Integer, Pair> mapU = new HashMap<>();59        for (int[] edge : children.get(u)) {60            int v = edge[0];61            if (v != heavyChild) {62                dfsSack(v); // Discard result, global answer is updated63            }64        }65 66        if (heavyChild != -1) {67            mapU = dfsSack(heavyChild);68            Map<Integer, Pair> newMapU = new HashMap<>();69            for (Map.Entry<Integer, Pair> entry : mapU.entrySet()) {70                int val = entry.getKey();71                Pair path = entry.getValue();72                long newLen = path.len + heavyChildLen;73                int newNodes = path.nodes + 1;74                if (val == nums[u]) {75                    updateGlobal(newLen, newNodes);76                } else {77                    newMapU.put(val, new Pair(newLen, newNodes));78                }79            }80            mapU = newMapU;81        }82 83        for (int[] edge : children.get(u)) {84            int v = edge[0];85            int length = edge[1];86            if (v != heavyChild) {87                Map<Integer, Pair> mapV = dfsSack(v);88                for (Map.Entry<Integer, Pair> entry : mapV.entrySet()) {89                    int val = entry.getKey();90                    Pair pathV = entry.getValue();91                    long newLen = pathV.len + length;92                    int newNodes = pathV.nodes + 1;93                    if (val == nums[u]) {94                        updateGlobal(newLen, newNodes);95                    } else {96                        if (!mapU.containsKey(val) || isBetter(newLen, newNodes, mapU.get(val))) {97                            mapU.put(val, new Pair(newLen, newNodes));98                        }99                    }100                }101            }102        }103 104        if (!mapU.containsKey(nums[u]) || isBetter(0, 1, mapU.get(nums[u]))) {105             mapU.put(nums[u], new Pair(0, 1));106        }107        108        for(Pair p : mapU.values()){109            updateGlobal(p.len, p.nodes);110        }111 112        return mapU;113    }114 115    private void updateGlobal(long len, int nodes) {116        if (len > maxLength) {117            maxLength = len;118            minNodes = nodes;119        } else if (len == maxLength) {120            minNodes = Math.min(minNodes, nodes);121        }122    }123 124    private boolean isBetter(long len1, int nodes1, Pair p2) {125        if (len1 > p2.len) return true;126        if (len1 == p2.len && nodes1 < p2.nodes) return true;127        return false;128    }129}

Complexity

Time

O(N log N). Each node's information is part of a map that is created and merged at most O(log N) times up the tree. Each merge operation takes time proportional to the size of the smaller map.

Space

O(N). The total size of all maps at any point in the recursion is bounded by O(N).

Trade-offs

Pros

Highly efficient, with a time complexity that can pass the given constraints.
It's a general and powerful technique for a class of tree problems where information needs to be aggregated from subtrees.

Cons

Significantly more complex to implement correctly compared to the simple DP.
The logic for merging and updating maps requires careful handling of multiple cases.

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.

← Previous

Previous problem

Next problem