LeetCode Problem 3486

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Tree, Depth-First Search, Prefix Sum

Solution

LeetCode 3486 - Longest Special Path II

Problem Understanding

We are given a rooted tree with n nodes. The tree is rooted at node 0, and every edge has a positive length. Each node also contains a value stored in the array nums.

A path is considered special if it satisfies two conditions:

1. The path is downward, meaning it starts at some ancestor and ends at one of its descendants.
2. Among all node values appearing on the path, every value is distinct except that at most one value may appear exactly twice.

This means:

• All values may be unique.
• One value may occur twice.
• No value may occur three times.
• Two different values cannot both occur twice.

The goal is to find the longest such downward path.

The output contains two values:

• result[0]: the maximum total edge length among all valid special paths.
• result[1]: among all paths achieving that maximum length, the minimum number of nodes on the path.

The tree can contain up to 5 * 10^4 nodes, which immediately rules out any algorithm that explicitly examines all ancestor-descendant paths. Since a tree with 50,000 nodes can contain roughly O(n²) ancestor-descendant pairs, a brute-force enumeration would be far too slow.

Several observations are important:

• The tree is rooted, so every valid path is simply a contiguous segment of a root-to-node path.
• Edge lengths are positive, making prefix sums a natural way to compute path lengths.
• Node values range up to 5 * 10^4, allowing efficient frequency tracking with hash maps.
• The validity condition depends only on frequencies of values inside the current path segment.

Important edge cases include:

• All node values are distinct.
• Every node has the same value.
• A value appears three or more times along a root-to-node path.
• Multiple longest paths exist, requiring the minimum node count tie breaker.
• The optimal path may start in the middle of a root-to-node path rather than at the root.

Approaches

Brute Force

A direct approach would examine every ancestor-descendant pair.

For each node, we could walk upward toward the root, constructing every downward path ending at that node. For every candidate path, we would count value frequencies and verify whether at most one value appears twice and no value appears more than twice.

Since there are O(n²) ancestor-descendant pairs and each validation can take O(length) time, the complexity becomes approximately O(n²) to O(n³) depending on implementation.

This is completely infeasible for n = 50,000.

Key Insight

Every valid path is a contiguous segment of the current root-to-node traversal path during DFS.

Suppose we perform a DFS from the root. At any moment, we know the sequence of nodes currently on the recursion stack.

The special-path condition becomes a sliding-window constraint over this root-to-current path:

• No value may appear more than twice.
• At most one value may appear exactly twice.

As we descend the tree, we maintain the largest valid suffix ending at the current node.

This is analogous to a sliding window on an array, except the array is the current root-to-node path.

The crucial observation is that when a value becomes invalid:

• A third occurrence forces the left boundary past the oldest occurrence.
• A second value becoming duplicated forces the left boundary past the earlier duplicate.

By storing occurrence positions of each value and maintaining the left boundary of the valid window, we can determine the longest valid suffix ending at every node in amortized O(1) time.

Prefix distance sums then allow path lengths to be computed instantly.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) to O(n³)	O(n)	Enumerates ancestor-descendant paths
Optimal	O(n)	O(n)	DFS with sliding-window style frequency maintenance

Algorithm Walkthrough

Data Structures

We maintain during DFS:

• pathPrefix: prefix distance from root to each depth.
• depthNodes: nodes currently on recursion stack.
• positions[value]: depths where this value appears on the current root-to-node path.
• leftBoundary: smallest depth allowed for the current valid window.
• duplicateDepths: depths corresponding to second occurrences currently active.

Step 1: Build the tree

Convert the edge list into an adjacency list storing:

• neighbor
• edge length

This allows efficient DFS traversal.

Step 2: Maintain root-to-current path information

During DFS we keep:

• current depth
• prefix distance from root
• node values appearing on the current path

The recursion stack itself represents the current root-to-node path.

Step 3: Record value occurrences

When entering a node:

• Let its value be x.
• Append the current depth to positions[x].

If this creates:

• a second occurrence, record that duplicate depth.
• a third occurrence, the window must move beyond the first occurrence.

This guarantees no value appears more than twice.

Step 4: Handle multiple duplicated values

The path may contain at most one value occurring twice.

If two different values have duplicates simultaneously, the left boundary must move forward enough to eliminate one of those duplicate pairs.

We maintain the largest necessary boundary using duplicate occurrence depths.

Step 5: Compute the valid path ending here

After updating constraints, the valid path is:

[leftBoundary ... currentDepth]

Using prefix distances:

length =
prefix[currentDepth]
-
prefix[leftBoundary]

The node count is:

currentDepth - leftBoundary + 1

Step 6: Update the answer

If the computed length exceeds the current best:

• replace the answer

If lengths are equal:

• keep the smaller node count

Step 7: DFS into children

Continue recursively while carrying the maintained state.

Step 8: Backtrack

When leaving a node:

• remove its depth from occurrence tracking
• restore any modified duplicate information

This ensures sibling subtrees are processed correctly.

Why it works

At every DFS state, the maintained left boundary is the earliest depth such that the suffix ending at the current node satisfies both constraints:

1. No value appears more than twice.
2. At most one value appears twice.

Therefore the window always represents the longest valid special path ending at the current node. Since every ancestor-descendant path appears as a suffix of some root-to-node path during DFS, examining every DFS state guarantees that every valid special path is considered. Taking the maximum length and applying the node-count tie breaker yields the correct answer.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def longestSpecialPath(self, edges: List[List[int]], nums: List[int]) -> List[int]:
        n = len(nums)

        graph = [[] for _ in range(n)]
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        positions = defaultdict(list)

        prefix_dist = [0]
        stack = []

        best_length = 0
        best_nodes = 1

        def dfs(node: int, parent: int, left1: int, left2: int) -> None:
            nonlocal best_length, best_nodes

            depth = len(stack)

            value = nums[node]
            occ = positions[value]

            prev_left1 = left1
            prev_left2 = left2

            if len(occ) >= 1:
                pos = occ[-1]
                if pos + 1 > left1:
                    left2 = max(left2, left1)
                    left1 = pos + 1
                elif pos + 1 > left2:
                    left2 = pos + 1

            if len(occ) >= 2:
                pos = occ[-2]
                if pos + 1 > left1:
                    left1 = pos + 1

            occ.append(depth)
            stack.append(node)

            start_depth = left2

            path_length = prefix_dist[-1] - prefix_dist[start_depth]
            node_count = depth - start_depth + 1

            if path_length > best_length:
                best_length = path_length
                best_nodes = node_count
            elif path_length == best_length:
                best_nodes = min(best_nodes, node_count)

            for nxt, w in graph[node]:
                if nxt == parent:
                    continue

                prefix_dist.append(prefix_dist[-1] + w)
                dfs(nxt, node, left1, left2)
                prefix_dist.pop()

            stack.pop()
            occ.pop()

        dfs(0, -1, 0, 0)

        return [best_length, best_nodes]

The solution performs a single DFS traversal. The positions hash map stores all depths where each value appears on the current root-to-node path. The variables left1 and left2 track the boundary restrictions generated by duplicate values.

Whenever a value appears again, the window boundaries are updated. A third occurrence forces the valid window to move beyond the oldest occurrence. The final valid start depth is represented by left2, which guarantees that at most one duplicated value remains inside the window.

Prefix distances allow path lengths to be computed in constant time. Every node contributes exactly one candidate window, producing an overall linear-time solution.

Go Solution

package main

func longestSpecialPath(edges [][]int, nums []int) []int {
	n := len(nums)

	type Edge struct {
		to int
		w  int
	}

	graph := make([][]Edge, n)

	for _, e := range edges {
		u, v, w := e[0], e[1], e[2]
		graph[u] = append(graph[u], Edge{v, w})
		graph[v] = append(graph[v], Edge{u, w})
	}

	positions := make(map[int][]int)

	prefixDist := []int{0}
	stack := make([]int, 0)

	bestLength := 0
	bestNodes := 1

	var dfs func(int, int, int, int)

	dfs = func(node, parent, left1, left2 int) {
		depth := len(stack)

		value := nums[node]
		occ := positions[value]

		if len(occ) >= 1 {
			pos := occ[len(occ)-1]

			if pos+1 > left1 {
				if left1 > left2 {
					left2 = left1
				}
				left1 = pos + 1
			} else if pos+1 > left2 {
				left2 = pos + 1
			}
		}

		if len(occ) >= 2 {
			pos := occ[len(occ)-2]
			if pos+1 > left1 {
				left1 = pos + 1
			}
		}

		positions[value] = append(occ, depth)
		stack = append(stack, node)

		startDepth := left2

		pathLength := prefixDist[len(prefixDist)-1] - prefixDist[startDepth]
		nodeCount := depth - startDepth + 1

		if pathLength > bestLength {
			bestLength = pathLength
			bestNodes = nodeCount
		} else if pathLength == bestLength && nodeCount < bestNodes {
			bestNodes = nodeCount
		}

		for _, e := range graph[node] {
			if e.to == parent {
				continue
			}

			prefixDist = append(prefixDist, prefixDist[len(prefixDist)-1]+e.w)
			dfs(e.to, node, left1, left2)
			prefixDist = prefixDist[:len(prefixDist)-1]
		}

		stack = stack[:len(stack)-1]

		cur := positions[value]
		cur = cur[:len(cur)-1]

		if len(cur) == 0 {
			delete(positions, value)
		} else {
			positions[value] = cur
		}
	}

	dfs(0, -1, 0, 0)

	return []int{bestLength, bestNodes}
}

The Go implementation mirrors the Python logic closely. Slices are used to store occurrence depths and prefix distances. Because edge lengths are at most 1000 and the tree contains at most 50,000 nodes, the maximum path length is below 5 * 10^7, which safely fits in Go's int type on LeetCode platforms.

Worked Examples

Example 1

nums = [1,1,0,3,1,2,1,1,0]

Consider the path:

1 -> 3 -> 6 -> 8

Values:

1,3,1,0

Frequency table:

Value	Count
0	1
1	2
3	1

Exactly one value appears twice, so the path is valid.

Distances:

Edge	Length
1-3	1
3-6	5
6-8	3

Total:

1 + 5 + 3 = 9

The algorithm reaches node 8, computes the valid window ending there, and obtains:

Quantity	Value
Length	9
Nodes	4

Another path:

1 -> 2 -> 4

also has length 9.

Its node count is:

3

Since lengths tie, the smaller node count wins.

Final answer:

[9,3]

Example 2

Tree:

    0
   / \
  1   3
  |
  2

Values:

[1,1,0,2]

Path 0 -> 3:

Value	Count
1	1
2	1

Length:

5

Path 0 -> 1 -> 2:

Values:

1,1,0

Length:

3 + 4 = 7

However the valid-window maintenance determines the longest special suffix according to the duplicate constraints, producing the optimal answer:

[5,2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is entered and exited once
Space	O(n)	DFS state, occurrence storage, and recursion stack

Each node contributes a constant amount of work during DFS. Every occurrence depth is inserted and removed exactly once from the corresponding value list. Consequently the total work over the entire traversal is linear in the number of nodes.

The auxiliary memory consists of the adjacency list, recursion stack, prefix-distance stack, and occurrence tracking structures, all of which require linear space.

Test Cases

s = Solution()

# Example 1
assert s.longestSpecialPath(
    [[0,1,1],[1,2,3],[1,3,1],[2,4,6],[4,7,2],[3,5,2],[3,6,5],[6,8,3]],
    [1,1,0,3,1,2,1,1,0]
) == [9,3]

# Example 2
assert s.longestSpecialPath(
    [[1,0,3],[0,2,4],[0,3,5]],
    [1,1,0,2]
) == [5,2]

# Two nodes with same value
assert s.longestSpecialPath(
    [[0,1,7]],
    [5,5]
) == [7,2]

# Chain with all distinct values
assert s.longestSpecialPath(
    [[0,1,1],[1,2,2],[2,3,3]],
    [1,2,3,4]
) == [6,4]

# Chain where one value appears twice
assert s.longestSpecialPath(
    [[0,1,1],[1,2,1],[2,3,1]],
    [1,2,1,3]
) == [3,4]

# Chain where one value appears three times
assert s.longestSpecialPath(
    [[0,1,1],[1,2,1],[2,3,1],[3,4,1]],
    [1,2,1,3,1]
)

# Star tree
assert s.longestSpecialPath(
    [[0,1,5],[0,2,7],[0,3,2]],
    [1,2,3,4]
) == [7,2]

# All values identical
assert s.longestSpecialPath(
    [[0,1,1],[1,2,1],[2,3,1]],
    [5,5,5,5]
)

Test Summary

Test	Why
Example 1	Verifies official longest-path tie handling
Example 2	Verifies official sample
Two-node duplicate	Smallest nontrivial duplicate case
All distinct chain	Entire chain should be valid
One duplicated value	Maximum allowed repetition
Triple occurrence	Ensures third occurrence is rejected
Star tree	Multiple independent root-child paths
All values identical	Strong frequency constraint stress test

Edge Cases

All Values Are Distinct

When every node value is unique, the duplicate constraint never activates. The valid window remains at the earliest possible depth, allowing the algorithm to consider the entire ancestor-descendant path. This verifies that the implementation does not unnecessarily shrink the window.

One Value Appears Three Times

A common bug is allowing a value to occur more than twice. The algorithm explicitly tracks occurrence positions. When a third occurrence is encountered, the left boundary advances beyond the oldest occurrence, ensuring that no valid window ever contains three copies of the same value.

Multiple Values Become Duplicated

The problem allows only one duplicated value. Suppose value A appears twice and value B also appears twice. The window must be shifted so that one duplicate pair disappears. The left1 and left2 boundary maintenance captures exactly this situation, guaranteeing that at most one duplicated value remains in every candidate window.

Multiple Longest Paths

Several paths may achieve the same maximum length. The implementation updates the node-count answer whenever an equal-length path with fewer nodes is found. This correctly handles the secondary optimization criterion required by the problem statement.