3425. Longest Special Path LeetCode Solution
In this guide, you will get 3425. Longest Special Path LeetCode Solution with the best time and space complexity. The solution to Longest Special Path 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.
Table of Contents
- Problem Statement
- Complexity Analysis
- Longest Special Path solution in C++
- Longest Special Path solution in Java
- Longest Special Path solution in Python
- Additional Resources
Problem Statement of Longest Special Path
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 * 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(n)
- Space Complexity: O(n)
3425. Longest Special Path 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, 0, 1, /*prefix=*/{0}, /*lastSeenDepth=*/{}, nums,
maxLength, minNodes);
return {maxLength, minNodes};
}
private:
void dfs(const vector<vector<pair<int, int>>>& graph, int u, int prev,
int leftBoundary, int currentDepth, 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]] = currentDepth;
leftBoundary = max(leftBoundary, prevDepth);
const int length = prefix.back() - prefix[leftBoundary];
const int nodes = currentDepth - leftBoundary;
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, currentDepth + 1, std::move(prefix),
std::move(lastSeenDepth), nums, maxLength, minNodes);
prefix.pop_back();
}
lastSeenDepth[nums[u]] = prevDepth;
}
};
/* code provided by PROGIEZ */3425. Longest Special Path 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, 0, 1, /*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, int leftBoundary,
int currentDepth, List<Integer> prefix, Map<Integer, Integer> lastSeenDepth,
int[] nums, int[] ans) {
final int prevDepth = lastSeenDepth.getOrDefault(nums[u], 0);
lastSeenDepth.put(nums[u], currentDepth);
leftBoundary = Math.max(leftBoundary, prevDepth);
final int length = prefix.get(prefix.size() - 1) - prefix.get(leftBoundary);
final int nodes = currentDepth - leftBoundary;
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, leftBoundary, currentDepth + 1, prefix, lastSeenDepth, nums, ans);
prefix.remove(prefix.size() - 1);
}
lastSeenDepth.put(nums[u], prevDepth);
}
}
// code provided by PROGIEZ3425. Longest Special Path LeetCode Solution in Python
class Solution:
def longestSpecialPath(
self,
edges: list[list[int]],
nums: list[int]
) -> list[int]:
graph = [[] for _ in range(len(nums))]
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
def dfs(
u: int,
prev: int,
leftBoundary: int,
currentDepth: int,
) -> None:
nonlocal maxLength, minNodes
prevDepth = lastSeenDepth.get(nums[u], 0)
lastSeenDepth[nums[u]] = currentDepth
leftBoundary = max(leftBoundary, prevDepth)
length = prefix[-1] - prefix[leftBoundary]
nodes = currentDepth - leftBoundary
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, currentDepth + 1)
prefix.pop()
lastSeenDepth[nums[u]] = prevDepth
maxLength = 0
minNodes = 1
prefix = [0]
lastSeenDepth = {}
dfs(0, -1, 0, 1)
return [maxLength, minNodes]
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.