Maximize the Number of Target Nodes After Connecting Trees I solution and explanation
Google
9 more videos on this problem
Maximize the Number of Target Nodes After Connecting Trees I | BFS | DFS | Leetcode 3372 | MIKcodestorywithMIK · 47:33 · 10K views
Maximize the Number of Target Nodes After Connecting Trees I | Leetcode 3372Techdose · 25:45 · 4K views
3372. Maximize the Number of Target Nodes After Connecting Trees I | Graph | BFS | GreedyAryan Mittal · 16:40 · 3K views
3372. Maximize the Number of Target Nodes After Connecting Trees I - Day 28/31 Leetcode May ChallengProgramming Live with Larry · 15:47 · 1K views
Maximize the Number of Target Nodes After Connecting Trees I |LeetCode 3372|Daily Leetcode potd|potdCode Thoughts · 20:52 · 804 views
LeetCode 3372 - Maximize the Number of Target Nodes After Connecting Trees I - JavaAlpha-Code · 12:11 · 380 views
3372. Maximize the Number of Target Nodes After Connecting Trees I | Leetcode Daily - PythonLeetcode Daily · 8:31 · 373 views
3372. Maximize the Number of Target Nodes After Connecting Trees I (Leetcode Medium)Programming Live with Larry · 18:57 · 246 views
Leetcode 3372 | Maximize the Number of Target Nodes After Connecting Trees I | Weekly Contest 426Road To FAANG · 10:58 · 200 views
3372. Maximize the Number of Target Nodes After Connecting Trees I | BFS | Greedy | LeetcodeRapid Syntax · 15:01 · 171 views
The problem
There exist two undirected trees with n and m nodes, with distinct labels in ranges [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] = [ai, bi] indicates that there is an edge between nodes ai and bi in the first tree and edges2[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the second tree. You are also given an integer k.
Node u is target to node v if the number of edges on the path from u to v is less than or equal to k. 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 target to node i of the first tree if you have 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.
Example 1:
Input: edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]], k = 2
Output: [9,7,9,8,8]
Explanation:
- For
i = 0, connect node 0 from the first tree to node 0 from the second tree. - For
i = 1, connect node 1 from the first tree to node 0 from the second tree. - For
i = 2, connect node 2 from the first tree to node 4 from the second tree. - For
i = 3, connect node 3 from the first tree to node 4 from the second tree. - For
i = 4, connect node 4 from the first tree to node 4 from the second tree.
Example 2:
Input: edges1 = [[0,1],[0,2],[0,3],[0,4]], edges2 = [[0,1],[1,2],[2,3]], k = 1
Output: [6,3,3,3,3]
Explanation:
For every i, connect node i of the first tree with any node of the second tree.
Constraints:
2 <= n, m <= 1000edges1.length == n - 1edges2.length == m - 1edges1[i].length == edges2[i].length == 2edges1[i] = [ai, bi]0 <= ai, bi < nedges2[i] = [ui, vi]0 <= ui, vi < m- The input is generated such that
edges1andedges2represent valid trees. 0 <= k <= 1000
Approach overview
Problem Overview: You are given two separate trees. You may connect exactly one node from the first tree to one node from the second tree with a new edge. For every node in the first tree, compute the maximum number of target nodes reachable within distance k after the connection is made. The goal is to choose the best node in the second tree so the reachable node count is maximized.
Approach 1: Breadth-First Search (BFS) Traversal (O(n^2 + m^2) time, O(n + m) space)
Treat both trees independently first. For each node in tree1, run a BFS to count how many nodes are within distance k. This produces an array where count1[i] represents reachable nodes if traversal stays inside tree1. Next, evaluate tree2 separately. Because one connecting edge consumes one step, nodes in tree2 must be within distance k-1 from the chosen connection node. Run BFS from every node in tree2 and compute how many nodes fall within distance k-1, then keep the maximum value. That maximum can be paired with any node in tree1 because you can always connect to the best node in tree2. The final answer for each node i becomes count1[i] + bestTree2. This approach works well because BFS naturally explores nodes level by level and stops once distance exceeds k. Tree traversal details rely on standard Breadth-First Search techniques.
Approach 2: Depth-First Search (DFS) with Memoization (O(n^2 + m^2) time, O(n + m) space)
The same distance counting can be implemented using recursive DFS. From each starting node, perform a depth-limited DFS that stops once the remaining distance becomes negative. Memoization can cache partial results for (node, remainingDistance) to avoid recomputing overlapping subtrees. This is useful when multiple DFS traversals revisit the same subtree with the same remaining distance. The logic mirrors the BFS approach: compute reachable counts within distance k for nodes in tree1 and within k-1 for nodes in tree2, then combine them using the maximum value from tree2. DFS implementations rely on adjacency lists and recursive traversal patterns from Depth-First Search on a tree.
Recommended for interviews: The BFS approach is usually expected. It is straightforward, avoids recursion depth issues, and clearly models the distance constraint. Showing the brute-force BFS from every node demonstrates understanding of tree traversal, while recognizing that the second tree only needs the global maximum shows the optimization insight interviewers look for.
Approach 1: Breadth-First Search (BFS) Based Approach
The idea is to calculate the number of target nodes for each node in both trees initially using a BFS traversal, given the constraint 'k'. After obtaining these counts, for each node in the first tree, try connecting it with every node in the second tree and compute the maximum target nodes considering the nodes in the second tree.
This approach leverages BFS to efficiently compute reachability within 'k' edges by using level-order traversal.
from collections import defaultdict, deque
def bfs_count(tree, n, k):
count = [0] * n
for i in range(n):
visited = [False] * n
queue = deque([(i, 0)])
while queue:
node, dist = queue.popleft()
if dist > k or visited[node]:
continue
visited[node] = True
count[i] += 1
for neighbor in tree[node]:
if not visited[neighbor]:
queue.append((neighbor, dist + 1))
return count
def maximize_target_nodes(edges1, edges2, k, n, m):
tree1 = defaultdict(list)
tree2 = defaultdict(list)
for u, v in edges1:
tree1[u].append(v)
tree1[v].append(u)
for u, v in edges2:
tree2[u].append(v)
tree2[v].append(u)
count1 = bfs_count(tree1, n, k)
count2 = bfs_count(tree2, m, k)
max_targets = [0] * n
for i in range(n):
max_adjacent_nodes = 0
for j in count2:
max_adjacent_nodes = max(max_adjacent_nodes, j)
max_targets[i] = count1[i] + max_adjacent_nodes
return max_targets
# Example usage:
edges1 = [[0,1],[0,2],[2,3],[2,4]]
edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]
k = 2
n = 5
m = 8
print(maximize_target_nodes(edges1, edges2, k, n, m))import java.util.*;
public class MaximizeTargets {
private static int[] bfsCount(List<Integer>[] adjList, int n, int k) {
int[] count = new int[n];
for (int i = 0; i < n; i++) {
boolean[] visited = new boolean[n];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, 0});
while (!queue.isEmpty()) {
int[] node = queue.poll();
int currentNode = node[0];
int distance = node[1];
if (distance > k || visited[currentNode]) continue;
visited[currentNode] = true;
count[i]++;
for (int neighbor : adjList[currentNode]) {
if (!visited[neighbor]) {
queue.offer(new int[]{neighbor, distance + 1});
}
}
}
}
return count;
}
public static int[] maximizeTargetNodes(int[][] edges1, int[][] edges2, int k, int n, int m) {
List<Integer>[] tree1 = new ArrayList[n];
List<Integer>[] tree2 = new ArrayList[m];
for (int i = 0; i < n; i++) tree1[i] = new ArrayList<>();
for (int i = 0; i < m; i++) tree2[i] = new ArrayList<>();
for (int[] edge : edges1) {
tree1[edge[0]].add(edge[1]);
tree1[edge[1]].add(edge[0]);
}
for (int[] edge : edges2) {
tree2[edge[0]].add(edge[1]);
tree2[edge[1]].add(edge[0]);
}
int[] count1 = bfsCount(tree1, n, k);
int[] count2 = bfsCount(tree2, m, k);
int[] maxTargets = new int[n];
for (int i = 0; i < n; i++) {
int maxAdjacentNodes = 0;
for (int count : count2) {
maxAdjacentNodes = Math.max(maxAdjacentNodes, count);
}
maxTargets[i] = count1[i] + maxAdjacentNodes;
}
return maxTargets;
}
public static void main(String[] args) {
int[][] edges1 = {{0, 1}, {0, 2}, {2, 3}, {2, 4}};
int[][] edges2 = {{0, 1}, {0, 2}, {0, 3}, {2, 7}, {1, 4}, {4, 5}, {4, 6}};
int n = 5;
int m = 8;
int k = 2;
System.out.println(Arrays.toString(maximizeTargetNodes(edges1, edges2, k, n, m)));
}
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODES 1000
void bfs_count(int **adj_list, int *size, int n, int k, int *count) {
int queue[MAX_NODES];
int front, rear;
int visited[MAX_NODES];
int distance[MAX_NODES];
for (int i = 0; i < n; i++) {
memset(visited, 0, sizeof(int) * n);
front = 0;
rear = 0;
queue[rear++] = i;
distance[i] = 0;
visited[i] = 1;
count[i] = 0;
while (front < rear) {
int node = queue[front++];
count[i]++;
for (int j = 0; j < size[node]; j++) {
int neighbor = adj_list[node][j];
if (!visited[neighbor] && distance[node] + 1 <= k) {
queue[rear++] = neighbor;
visited[neighbor] = 1;
distance[neighbor] = distance[node] + 1;
}
}
}
}
}
int *maximize_target_nodes(int edges1[][2], int edges2[][2], int n1, int m1, int k, int n, int m) {
int **adj_list1 = (int **)calloc(n, sizeof(int *));
int **adj_list2 = (int **)calloc(m, sizeof(int *));
int size1[MAX_NODES] = {0};
int size2[MAX_NODES] = {0};
for (int i = 0; i < n; i++) {
adj_list1[i] = (int *)calloc(n - 1, sizeof(int));
}
for (int i = 0; i < m; i++) {
adj_list2[i] = (int *)calloc(m - 1, sizeof(int));
}
for (int i = 0; i < n1; i++) {
int u = edges1[i][0];
int v = edges1[i][1];
adj_list1[u][size1[u]++] = v;
adj_list1[v][size1[v]++] = u;
}
for (int i = 0; i < m1; i++) {
int u = edges2[i][0];
int v = edges2[i][1];
adj_list2[u][size2[u]++] = v;
adj_list2[v][size2[v]++] = u;
}
int count1[MAX_NODES] = {0};
int count2[MAX_NODES] = {0};
bfs_count(adj_list1, size1, n, k, count1);
bfs_count(adj_list2, size2, m, k, count2);
int *max_targets = (int *)calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
int max_adjacent_nodes = 0;
for (int j = 0; j < m; j++) {
if (count2[j] > max_adjacent_nodes) {
max_adjacent_nodes = count2[j];
}
}
max_targets[i] = count1[i] + max_adjacent_nodes;
}
for (int i = 0; i < n; i++) {
free(adj_list1[i]);
}
for (int i = 0; i < m; i++) {
free(adj_list2[i]);
}
free(adj_list1);
free(adj_list2);
return max_targets;
}
int main() {
int n = 5, m = 8, k = 2;
int edges1[4][2] = {{0, 1}, {0, 2}, {2, 3}, {2, 4}};
int edges2[7][2] = {{0, 1}, {0, 2}, {0, 3}, {2, 7}, {1, 4}, {4, 5}, {4, 6}};
int *result = maximize_target_nodes(edges1, edges2, 4, 7, k, n, m);
for (int i = 0; i < n; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}This solution involves breaking down the existing trees into adjacency lists and calculating the reachable node counts within 'k' distance using BFS. Subsequently, it integrates both trees by evaluating each node's reachability from the first to the second tree, providing a combined reachability value for node targets.
Time Complexity: O(N * M * K), where N is the number of nodes in the first tree, M is the number of nodes in the second tree, and K is the target distance threshold.
Space Complexity: O(N + M), considering the space for adjacency lists and auxiliary structures used during traversal.
Approach 2: Depth-First Search (DFS) Based Approach with Memoization
This approach leverages DFS to find the number of target nodes reachable within 'k' from each node, utilizing memoization to store already computed results. By efficiently storing the DFS traversal results, we reduce redundant calculations, improving performance for larger graphs.
The integration of memoization with depth-first traversal provides an efficient matrix to determine targets when interlinking trees.
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> DFS_count(vector<vector<int>>& tree, int n, int k) {
vector<vector<int>> memo(n, vector<int>(k + 1, -1));
vector<int> count(n, 0);
function<int(int, int, int)> dfs = [&](int node, int parent, int dist) {
if (dist > k) return 0;
if (memo[node][dist] != -1) return memo[node][dist];
int result = 1; // self is always counted
for (int neighbor : tree[node]) {
if (neighbor != parent) {
result += dfs(neighbor, node, dist + 1);
}
}
return memo[node][dist] = result;
};
for (int i = 0; i < n; ++i) {
count[i] = dfs(i, -1, 0);
}
return count;
}
vector<int> maximize_target_nodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k, int n, int m) {
vector<vector<int>> tree1(n), tree2(m);
for (auto& edge : edges1) {
tree1[edge[0]].push_back(edge[1]);
tree1[edge[1]].push_back(edge[0]);
}
for (auto& edge : edges2) {
tree2[edge[0]].push_back(edge[1]);
tree2[edge[1]].push_back(edge[0]);
}
vector<int> count1 = DFS_count(tree1, n, k);
vector<int> count2 = DFS_count(tree2, m, k);
vector<int> result(n, 0);
for (int i = 0; i < n; i++) {
result[i] = *max_element(count2.begin(), count2.end()) + count1[i];
}
return result;
}
int main() {
vector<vector<int>> edges1 = {{0, 1}, {0, 2}, {2, 3}, {2, 4}};
vector<vector<int>> edges2 = {{0, 1}, {0, 2}, {0, 3}, {2, 7}, {1, 4}, {4, 5}, {4, 6}};
int k = 2;
vector<int> result = maximize_target_nodes(edges1, edges2, k, 5, 8);
for (int num : result) cout << num << " ";
cout<<endl;
return 0;
}const dfsCount = (tree, n, k) => {
const memo = Array.from({ length: n }, () => Array(k + 1).fill(-1));
const count = Array(n).fill(0);
const dfs = (node, parent, dist) => {
if (dist > k) return 0;
if (memo[node][dist] !== -1) return memo[node][dist];
let result = 1;
for (const neighbor of tree[node]) {
if (neighbor !== parent) {
result += dfs(neighbor, node, dist + 1);
}
}
return (memo[node][dist] = result);
};
for (let i = 0; i < n; i++) {
count[i] = dfs(i, -1, 0);
}
return count;
};
const maximizeTargetNodes = (edges1, edges2, k, n, m) => {
const tree1 = Array.from({ length: n }, () => []);
const tree2 = Array.from({ length: m }, () => []);
for (const [u, v] of edges1) {
tree1[u].push(v);
tree1[v].push(u);
}
for (const [u, v] of edges2) {
tree2[u].push(v);
tree2[v].push(u);
}
const count1 = dfsCount(tree1, n, k);
const count2 = dfsCount(tree2, m, k);
const result = Array(n);
for (let i = 0; i < n; i++) {
result[i] = Math.max(...count2) + count1[i];
}
return result;
};
// Usage example:
console.log(maximizeTargetNodes(
[[0, 1], [0, 2], [2, 3], [2, 4]],
[[0, 1], [0, 2], [0, 3], [2, 7], [1, 4], [4, 5], [4, 6]],
2,
5,
8
));This solution builds trees using undirected edges and applies DFS with memoization to calculate reachable nodes efficiently within 'k'. The results are aggregated by finding the potential target nodes the first tree could exploit from the second tree.
Time Complexity: O(N * M), where N and M represent the number of nodes in the respective trees.
Space Complexity: O(N * K) due to memoization array usage.
Approach 3: Enumeration + DFS
According to the problem description, to maximize the number of target nodes for node i, we must connect node i to one of the nodes j in the second tree. Therefore, the number of target nodes for node i can be divided into two parts:
- In the first tree, the number of nodes reachable from node
iwithin a depth ofk. - In the second tree, the maximum number of nodes reachable from any node
jwithin a depth ofk - 1.
Thus, we can first calculate the number of nodes reachable within a depth of k - 1 for each node in the second tree. Then, we enumerate each node i in the first tree, calculate the sum of the two parts mentioned above, and take the maximum value.
The time complexity is O(n^2 + m^2), and the space complexity is O(n + m). Here, n and m are the number of nodes in the two trees, respectively.
function maxTargetNodes(edges1: number[][], edges2: number[][], k: number): number[] {
const g2 = build(edges2);
const m = edges2.length + 1;
let t = 0;
for (let i = 0; i < m; i++) {
t = Math.max(t, dfs(g2, i, -1, k - 1));
}
const g1 = build(edges1);
const n = edges1.length + 1;
const ans = Array(n).fill(t);
for (let i = 0; i < n; i++) {
ans[i] += dfs(g1, i, -1, k);
}
return ans;
}
function build(edges: number[][]): number[][] {
const n = edges.length + 1;
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
return g;
}
function dfs(g: number[][], a: number, fa: number, d: number): number {
if (d < 0) {
return 0;
}
let cnt = 1;
for (const b of g[a]) {
if (b !== fa) {
cnt += dfs(g, b, a, d - 1);
}
}
return cnt;
}public class Solution {
public int[] MaxTargetNodes(int[][] edges1, int[][] edges2, int k) {
var g2 = Build(edges2);
int m = edges2.Length + 1;
int t = 0;
for (int i = 0; i < m; i++) {
t = Math.Max(t, Dfs(g2, i, -1, k - 1));
}
var g1 = Build(edges1);
int n = edges1.Length + 1;
var ans = new int[n];
Array.Fill(ans, t);
for (int i = 0; i < n; i++) {
ans[i] += Dfs(g1, i, -1, k);
}
return ans;
}
private List<int>[] Build(int[][] edges) {
int n = edges.Length + 1;
var g = new List<int>[n];
for (int i = 0; i < n; i++) {
g[i] = new List<int>();
}
foreach (var e in edges) {
int a = e[0], b = e[1];
g[a].Add(b);
g[b].Add(a);
}
return g;
}
private int Dfs(List<int>[] g, int a, int fa, int d) {
if (d < 0) {
return 0;
}
int cnt = 1;
foreach (var b in g[a]) {
if (b != fa) {
cnt += Dfs(g, b, a, d - 1);
}
}
return cnt;
}
}func maxTargetNodes(edges1 [][]int, edges2 [][]int, k int) []int {
g2 := build(edges2)
m := len(edges2) + 1
t := 0
for i := 0; i < m; i++ {
t = max(t, dfs(g2, i, -1, k-1))
}
g1 := build(edges1)
n := len(edges1) + 1
ans := make([]int, n)
for i := 0; i < n; i++ {
ans[i] = t + dfs(g1, i, -1, k)
}
return ans
}
func build(edges [][]int) [][]int {
n := len(edges) + 1
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
return g
}
func dfs(g [][]int, a, fa, d int) int {
if d < 0 {
return 0
}
cnt := 1
for _, b := range g[a] {
if b != fa {
cnt += dfs(g, b, a, d-1)
}
}
return cnt
}impl Solution {
pub fn max_target_nodes(edges1: Vec<Vec<i32>>, edges2: Vec<Vec<i32>>, k: i32) -> Vec<i32> {
fn build(edges: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let n = edges.len() + 1;
let mut g = vec![vec![]; n];
for e in edges {
let a = e[0] as usize;
let b = e[1] as usize;
g[a].push(b as i32);
g[b].push(a as i32);
}
g
}
fn dfs(g: &Vec<Vec<i32>>, a: usize, fa: i32, d: i32) -> i32 {
if d < 0 {
return 0;
}
let mut cnt = 1;
for &b in &g[a] {
if b != fa {
cnt += dfs(g, b as usize, a as i32, d - 1);
}
}
cnt
}
let g2 = build(&edges2);
let m = edges2.len() + 1;
let mut t = 0;
for i in 0..m {
t = t.max(dfs(&g2, i, -1, k - 1));
}
let g1 = build(&edges1);
let n = edges1.len() + 1;
let mut ans = vec![t; n];
for i in 0..n {
ans[i] += dfs(&g1, i, -1, k);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Based Approach | Time Complexity: O(N * M * K), where N is the number of nodes in the first tree, M is the number of nodes in the second tree, and K is the target distance threshold. Space Complexity: O(N + M), considering the space for adjacency lists and auxiliary structures used during traversal. |
| Depth-First Search (DFS) Based Approach with Memoization | Time Complexity: O(N * M), where N and M represent the number of nodes in the respective trees. |
| Enumeration + DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS Traversal from Every Node | O(n^2 + m^2) | O(n + m) | Best general approach for medium constraints and easiest to implement |
| DFS with Memoization | O(n^2 + m^2) | O(n + m) | Useful when recursion with distance pruning is preferred or when caching subtree results |
Frequently asked questions
Is Maximize the Number of Target Nodes After Connecting Trees I easy or hard?
The problem is rated Medium. The main challenge is recognizing that the optimal node from the second tree can be computed independently and reused for every node in the first tree, which simplifies the overall logic.
Maximize the Number of Target Nodes After Connecting Trees I Python/Java solution
Implementations typically build adjacency lists for both trees and run BFS from each node to count reachable nodes within the allowed distance. The same logic works in Python, Java, C, or C++ because the algorithm relies only on graph traversal and queue operations.
How to solve Maximize the Number of Target Nodes After Connecting Trees I in O(n)?
A strict O(n) solution is difficult because the problem requires distance-based counts from multiple nodes. Most accepted implementations run BFS or DFS from each node to count nodes within distance k. Optimizations mainly focus on reusing the maximum value from tree2 rather than recomputing combinations for every node.
What is the best approach for Maximize the Number of Target Nodes After Connecting Trees I?
The most practical approach is running Breadth-First Search (BFS) from each node in both trees. Compute how many nodes in tree1 are within distance k and find the maximum number of nodes reachable within distance k-1 from any node in tree2. Combining these values gives the optimal result for every node in tree1.
Is Maximize the Number of Target Nodes After Connecting Trees I asked at Google/Amazon/Meta?
Tree traversal and distance-counting problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. The exact problem may not appear verbatim, but BFS or DFS on trees with distance constraints is a common interview pattern.
What data structure is used in Maximize the Number of Target Nodes After Connecting Trees I?
The solution primarily uses adjacency lists to represent both trees, along with a queue for BFS or recursion stack for DFS. These structures allow efficient traversal and distance tracking while exploring neighbors in the tree.
What is the time complexity of Maximize the Number of Target Nodes After Connecting Trees I?
The typical solution runs BFS or DFS from every node in each tree. For trees with n and m nodes, this results in O(n^2 + m^2) time in the worst case, with O(n + m) auxiliary space for adjacency lists and traversal queues.