LeetCode 3372: Maximize the Number of Target Nodes After Connecting Trees I Solution

Master LeetCode problem 3372 (Maximize the Number of Target Nodes After Connecting Trees I), a medium 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.

3372. Maximize the Number of Target Nodes After Connecting Trees I

Medium

Tree Depth-First Search Breadth-First Search

Problem Explanation

Explanation:

To solve this problem, we need to find the maximum number of nodes target to each node in the first tree after connecting it to a node in the second tree. We can achieve this by simulating the process for each node in the first tree.

We create a graph for each tree based on the given edges.
For each node in the first tree, we iterate over all nodes in the second tree and calculate the number of nodes that are target to the current node with a path length <= k.
We track the maximum number of nodes target to each node in the first tree.
Return the array with the maximum number of nodes target to each node in the first tree.

Time complexity: O(n * m) where n is the number of nodes in the first tree and m is the number of nodes in the second tree. Space complexity: O(n + m) for storing the graphs of both trees.

Solution Code

class Solution {
    public int[] countSubTrees(int n, int[][] edges1, int[][] edges2, int k) {
        List<List<Integer>> graph1 = buildGraph(n, edges1);
        List<List<Integer>> graph2 = buildGraph(n, edges2);
        
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = countNodes(graph1, graph2, i, k);
        }
        
        return result;
    }
    
    private List<List<Integer>> buildGraph(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        return graph;
    }
    
    private int countNodes(List<List<Integer>> graph1, List<List<Integer>> graph2, int node, int k) {
        boolean[] visited = new boolean[graph1.size()];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{node, 0});
        int count = 0;
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int currNode = curr[0];
            int currDist = curr[1];
            
            if (currDist > k) {
                break;
            }
            
            if (!visited[currNode]) {
                visited[currNode] = true;
                count++;
                
                for (int neighbor : graph1.get(currNode)) {
                    if (!visited[neighbor]) {
                        queue.offer(new int[]{neighbor, currDist + 1});
                    }
                }
                
                for (int neighbor : graph2.get(currNode)) {
                    if (!visited[neighbor]) {
                        queue.offer(new int[]{neighbor, currDist + 1});
                    }
                }
            }
        }
        
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3372 (Maximize the Number of Target Nodes After Connecting Trees I)?

This page provides optimized solutions for LeetCode problem 3372 (Maximize the Number of Target Nodes After Connecting Trees I) 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 3372 (Maximize the Number of Target Nodes After Connecting Trees I)?

The time complexity for LeetCode 3372 (Maximize the Number of Target Nodes After Connecting Trees I) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3372 on DevExCode?

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

Back to LeetCode Solutions