Facebook Pixel

3373. Maximize the Number of Target Nodes After Connecting Trees II

HardTreeDepth-First SearchBreadth-First Search
Leetcode Link

Problem Description

There exist two undirected trees with n and m nodes, labeled from [0, n - 1] and [0, m - 1], respectively.

You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the first tree and edges2[i] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i in the second tree.

Node u is target to node v if the number of edges on the path from u to v is even. Note that a node is always target to itself.

Return an array of n integers answer, where answer[i] is the maximum possible number of nodes that are target to node i of the first tree if you had to connect one node from the first tree to another node in the second tree.

Note that queries are independent from each other. That is, for every query you will remove the added edge before proceeding to the next query.

Intuition

The task is to determine how many nodes in the first tree can be target for a given node based on its path distance parity (even or odd) with nodes in the second tree. The main challenge is efficiently computing this for each node in the first tree.

To solve this:

  1. Understand Path Parity:

    • A path is said to be target if the number of edges is even.
    • Each node is a target to itself, as the distance is zero (even).

  2. Use of Depth-First Search (DFS):

    • DFS helps calculate the number of nodes at each parity level (even or odd) in both trees.

  3. Calculate Parity Depth Counts:

    • Run DFS on both trees to calculate the count of even and odd depth nodes (cnt1 and cnt2).
    • For each node in the first tree:
      • The total number of target nodes is the sum of nodes with the same depth parity in the first tree and the maximum number of nodes from the second tree with any depth parity (as connecting nodes removes any restrictions on parity).

The solution cleverly uses the parity of depths, balancing counts for even and odd levels to determine where additional connections maximize the target nodes.

Learn more about Tree, Depth-First Search and Breadth-First Search patterns.

Solution Approach

The solution employs a Depth-First Search (DFS) strategy to determine the number of nodes in each tree that have the same depth parity—either even or odd. Here’s a step-by-step breakdown of the approach:

  1. Building the Graph:

    • We start by constructing adjacency lists for both trees from the given edge lists. This is done using a helper function build(edges), which initializes a list of lists to represent the adjacency list for each tree.

  2. Depth Calculation Using DFS:

    • Implement a DFS function dfs(g, node, parent, c, depth, cnt) that traverses a tree. This function updates the depth parity array c and increments the count of nodes at even (cnt[0]) or odd (cnt[1]) depths.
    • Depth is alternated using depth ^ 1 (a bitwise XOR operation) to switch between even and odd as we traverse down a level in the tree.

  3. DFS Execution on Both Trees:

    • Perform DFS on the second tree to compute the number of nodes with even and odd depth parities (cnt2).
    • Similarly, execute DFS on the first tree to acquire the depth parity counts for its nodes (cnt1).

  4. Determine Maximum Target Nodes:

    • Calculate t as the maximum of cnt2, which represents the maximum number of nodes at either even or odd levels in the second tree.
    • For each node i in the first tree, compute the number of target nodes as t + cnt1[c1[i]], where cnt1[c1[i]] is the count of nodes in the first tree with the same depth parity as node i.

This method efficiently analyzes the problem using parity logic, thereby achieving an optimal solution to the problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider two simple trees represented with their edge lists:

Tree 1:

  • Nodes: {0, 1, 2}
  • Edges: [[0, 1], [1, 2]]

Tree 2:

  • Nodes: {0, 1, 2}
  • Edges: [[0, 1], [1, 2]]

Step 1: Building the Graph

Construct adjacency lists for both trees:

  • Tree 1 adjacency list: [[1], [0, 2], [1]]
  • Tree 2 adjacency list: [[1], [0, 2], [1]]

Step 2: Depth Calculation Using DFS

Perform a DFS on Tree 1 starting from node 0:

  • Node 0 has a depth parity of 0 (even)
  • Node 1 has a depth parity of 1 (odd)
  • Node 2 has a depth parity of 0 (even)

This results in cnt1 = [2, 1], meaning 2 nodes with even parity and 1 node with odd parity in Tree 1.

Perform a DFS on Tree 2 starting from node 0:

  • Node 0 has a depth parity of 0 (even)
  • Node 1 has a depth parity of 1 (odd)
  • Node 2 has a depth parity of 0 (even)

This results in cnt2 = [2, 1], meaning 2 nodes with even parity and 1 node with odd parity in Tree 2.

Step 3: Determine Maximum Target Nodes

Calculate t as the maximum of cnt2, which is 2.

For each node i in Tree 1, compute:

  • Node 0: t + cnt1[c1[0]] = 2 + 2 = 4
  • Node 1: t + cnt1[c1[1]] = 2 + 1 = 3
  • Node 2: t + cnt1[c1[2]] = 2 + 2 = 4

Final Result

The array answer for Tree 1 is [4, 3, 4], indicating the maximum number of nodes that can be targeted from each node in Tree 1 when connected to Tree 2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:
5        # Helper function to build adjacency list from edges
6        def build(edges: List[List[int]]) -> List[List[int]]:
7            n = len(edges) + 1  # Number of nodes
8            adjacency_list = [[] for _ in range(n)]
9            for u, v in edges:
10                adjacency_list[u].append(v)  # Add edge u to v
11                adjacency_list[v].append(u)  # Add edge v to u (undirected)
12            return adjacency_list
13
14        # Depth-First Search to label nodes and count nodes in each label
15        def dfs(adjacency_list: List[List[int]], current: int, parent: int, labels: List[int], label: int, label_count: List[int]):
16            labels[current] = label  # Assign label to current node
17            label_count[label] += 1  # Increment count of current label
18            for neighbor in adjacency_list[current]:
19                if neighbor != parent:  # Avoid revisiting the parent node
20                    dfs(adjacency_list, neighbor, current, labels, label ^ 1, label_count)  # Alternate label with XOR
21
22        # Build adjacency lists for given edge sets
23        graph1 = build(edges1)
24        graph2 = build(edges2)
25
26        # Initialize node counts and labels for two graphs
27        num_nodes1, num_nodes2 = len(graph1), len(graph2)
28        labels1 = [0] * num_nodes1
29        labels2 = [0] * num_nodes2
30        label_count1 = [0, 0]
31        label_count2 = [0, 0]
32
33        # Perform DFS on both graphs to label them
34        dfs(graph2, 0, -1, labels2, 0, label_count2)
35        dfs(graph1, 0, -1, labels1, 0, label_count1)
36
37        # Calculate maximum number of target nodes
38        max_label_count2 = max(label_count2)
39        result = [max_label_count2 + label_count1[labels1[i]] for i in range(num_nodes1)]
40      
41        return result
42
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public int[] maxTargetNodes(int[][] edges1, int[][] edges2) {
7        // Build adjacency lists for both graphs
8        List<Integer>[] graph1 = build(edges1);
9        List<Integer>[] graph2 = build(edges2);
10
11        int n = graph1.length;
12        int m = graph2.length;
13
14        // Arrays to store color groups for each node
15        int[] colorGroup1 = new int[n];
16        int[] colorGroup2 = new int[m];
17
18        // Arrays to count nodes in each color group
19        int[] count1 = new int[2];
20        int[] count2 = new int[2];
21
22        // Perform DFS on graph2 and fill colorGroup2 and count2
23        dfs(graph2, 0, -1, colorGroup2, 0, count2);
24
25        // Perform DFS on graph1 and fill colorGroup1 and count1
26        dfs(graph1, 0, -1, colorGroup1, 0, count1);
27
28        // Find the maximum of the two color group counts in graph2
29        int maxColorGroup = Math.max(count2[0], count2[1]);
30
31        // Array to store the result
32        int[] result = new int[n];
33
34        // Calculate the result for each node in graph1
35        for (int i = 0; i < n; ++i) {
36            result[i] = maxColorGroup + count1[colorGroup1[i]];
37        }
38
39        return result;
40    }
41
42    private List<Integer>[] build(int[][] edges) {
43        int n = edges.length + 1;
44        List<Integer>[] graph = new List[n];
45        Arrays.setAll(graph, i -> new ArrayList<>());
46        for (var edge : edges) {
47            int a = edge[0], b = edge[1];
48            graph[a].add(b);
49            graph[b].add(a);
50        }
51        return graph;
52    }
53
54    private void dfs(List<Integer>[] graph, int currentNode, int parentNode, int[] colorGroup, int depth, int[] count) {
55        // Assign the depth as the color group to currentNode
56        colorGroup[currentNode] = depth;
57
58        // Increase the count for the current color group
59        count[depth]++;
60
61        for (int neighbor : graph[currentNode]) {
62            if (neighbor != parentNode) {
63                // Alternate depth (0 to 1 or 1 to 0) and continue DFS on the neighbor
64                dfs(graph, neighbor, currentNode, colorGroup, depth ^ 1, count);
65            }
66        }
67    }
68}
69
1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
9        // Build graphs from edge lists
10        vector<vector<int>> graph1 = build(edges1);
11        vector<vector<int>> graph2 = build(edges2);
12
13        int n = graph1.size(); // Number of nodes in graph1
14        int m = graph2.size(); // Number of nodes in graph2
15
16        // Initialize color vectors and count vectors for both graphs
17        vector<int> color1(n, 0);
18        vector<int> color2(m, 0);
19        vector<int> count1(2, 0);
20        vector<int> count2(2, 0);
21
22        // Perform depth-first search on both graphs starting from node 0
23        dfs(graph2, 0, -1, color2, 0, count2);
24        dfs(graph1, 0, -1, color1, 0, count1);
25
26        // Determine the maximum between the two calculated counts for graph2
27        int maxCount = max(count2[0], count2[1]);
28
29        // Initialize answer vector
30        vector<int> answer(n);
31
32        // Calculate the result for each node in graph1 based on its color
33        for (int i = 0; i < n; ++i) {
34            answer[i] = maxCount + count1[color1[i]];
35        }
36
37        return answer;
38    }
39
40private:
41    // Builds an adjacency list from given edges
42    vector<vector<int>> build(const vector<vector<int>>& edges) {
43        int numNodes = edges.size() + 1;
44        vector<vector<int>> graph(numNodes);
45
46        for (const auto& edge : edges) {
47            int nodeA = edge[0];
48            int nodeB = edge[1];
49
50            // Add bidirectional edges to the graph
51            graph[nodeA].push_back(nodeB);
52            graph[nodeB].push_back(nodeA);
53        }
54
55        return graph;
56    }
57
58    // Depth-first search function to color the graph and count nodes in two groups
59    void dfs(const vector<vector<int>>& graph, int node, int parentNode, vector<int>& color, int depth, vector<int>& count) {
60        // Color current node and update count
61        color[node] = depth;
62        count[depth]++;
63      
64        // Recursively visit all the neighbors
65        for (int neighbor : graph[node]) {
66            if (neighbor != parentNode) {
67                dfs(graph, neighbor, node, color, depth ^ 1, count);
68            }
69        }
70    }
71};
72
1// Function to compute the maximum target nodes from two sets of edges
2function maxTargetNodes(edges1: number[][], edges2: number[][]): number[] {
3    // Build graph representations from the edge lists
4    const g1 = build(edges1);
5    const g2 = build(edges2);
6
7    // Determine the number of nodes in each graph
8    const [n, m] = [g1.length, g2.length];
9
10    // Arrays to store colors (or depth levels) of nodes during DFS traversal
11    const colors1 = Array(n).fill(0); // For graph g1
12    const colors2 = Array(m).fill(0); // For graph g2
13
14    // Arrays to count the number of nodes at each depth for each graph
15    const count1 = [0, 0];
16    const count2 = [0, 0];
17
18    // Perform DFS on both graphs to populate colors and count arrays
19    dfs(g2, 0, -1, colors2, 0, count2);
20    dfs(g1, 0, -1, colors1, 0, count1);
21
22    // Find the maximum number of nodes at any depth in g2
23    const maxFromG2 = Math.max(...count2);
24
25    // Calculate the result for each node in g1
26    const result = Array(n);
27    for (let i = 0; i < n; i++) {
28        result[i] = maxFromG2 + count1[colors1[i]];
29    }
30
31    return result;
32}
33
34// Helper function to build graph as an adjacency list from edge pairs
35function build(edges: number[][]): number[][] {
36    const n = edges.length + 1; // Number of nodes
37    const graph: number[][] = Array.from({ length: n }, () => []);
38
39    // Populating the adjacency list
40    for (const [a, b] of edges) {
41        graph[a].push(b);
42        graph[b].push(a);
43    }
44
45    return graph;
46}
47
48// Depth-First Search to determine the depth/color of nodes
49function dfs(graph: number[][], node: number, parent: number, colors: number[], depth: number, count: number[]): void {
50    colors[node] = depth;    // Assign depth as color to node
51    count[depth]++;          // Increment count of nodes at current depth
52
53    // Recursively visit all adjacent nodes
54    for (const neighbor of graph[node]) {
55        if (neighbor !== parent) {
56            // Alternate depth between 0 and 1 by using XOR operation for bipartite coloring
57            dfs(graph, neighbor, node, colors, depth ^ 1, count);
58        }
59    }
60}
61

Time and Space Complexity

The time complexity of the code is O(n + m), where n is the number of nodes in the first tree (edges1) and m is the number of nodes in the second tree (edges2). This results from the following operations:

  • The build function iterates over all edges to construct the adjacency list, which takes O(n + m).
  • The dfs function is a depth-first search that also visits each node exactly once, resulting in a complexity of O(n + m) for each tree.

The space complexity of the code is O(n + m) as well, due to:

  • The construction of adjacency lists g1 and g2, which require O(n) and O(m) space respectively.
  • The color arrays c1 and c2, each of size proportional to the number of nodes in their respective trees.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More