LeetCode 2421: Number of Good Paths
LeetCode 2421 Solution Explanation
Explanation:
To solve this problem, we can perform a depth-first search (DFS) traversal on the tree starting from each node. While traversing, we keep track of the count of good paths starting from the current node. We also maintain a dictionary to store the count of values encountered on the path from the current node to the root node.
At each node, we iterate over its neighbors and recursively call the DFS function for each neighbor while updating the count of good paths and the dictionary storing values encountered on the path.
The count of good paths from a node to its parent can be calculated based on the values encountered on the path. We increment the count by the number of good paths starting from the current node and add the count of paths that can be formed by connecting the current node to its ancestors with the same value.
Finally, we sum up the counts of good paths starting from each node to get the total number of distinct good paths in the tree.
Time Complexity: O(n) where n is the number of nodes in the tree. Space Complexity: O(n) for the recursion stack and dictionary storing values encountered on the path.
LeetCode 2421 Solutions in Java, C++, Python
class Solution {
int count = 0;
public int countGoodPaths(int[] vals, int[][] edges) {
Map<Integer, Integer>[] paths = new HashMap[vals.length];
for (int i = 0; i < vals.length; i++) {
paths[i] = new HashMap<>();
}
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < vals.length; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
dfs(0, -1, vals, paths, graph);
return count;
}
private void dfs(int node, int parent, int[] vals, Map<Integer, Integer>[] paths, List<List<Integer>> graph) {
Map<Integer, Integer> path = new HashMap<>();
path.put(vals[node], 1);
for (int neighbor : graph.get(node)) {
if (neighbor == parent) continue;
dfs(neighbor, node, vals, paths, graph);
for (Map.Entry<Integer, Integer> entry : paths[neighbor].entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
int newPathCount = path.getOrDefault(key, 0) + value;
path.put(key, newPathCount);
if (key == vals[node]) {
count += value;
}
}
}
paths[node] = path;
}
}Interactive Code Editor for LeetCode 2421
Improve Your LeetCode 2421 Solution
Use the editor below to refine the provided solution for LeetCode 2421. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...