LeetCode 2421: Number of Good Paths Solution

Master LeetCode problem 2421 (Number of Good Paths), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2421. Number of Good Paths

Hard

Array Hash Table Tree Union Find Graph Sorting

Problem 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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2421 (Number of Good Paths)?

This page provides optimized solutions for LeetCode problem 2421 (Number of Good Paths) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2421 (Number of Good Paths)?

The time complexity for LeetCode 2421 (Number of Good Paths) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2421 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2421 in Java, C++, or Python.

Back to LeetCode Solutions