Maximize the Number of Target Nodes After Connecting Trees I Solution
Maximize the Number of Target Nodes After Connecting Trees I solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximize the Number of Target Nodes After Connecting Trees I is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are two undirected trees: the first has n nodes labelled 0 to n - 1 with edges edges1, the second has m nodes labelled 0 to m - 1 with edges edges2. You are also given an integer k.
Node u is a target of node v if the path between them has at most k edges. A node is always a target of itself.
For every node i of the first tree, you may add one edge joining any node of the first tree to any node of the second tree, and then count the targets of i in the combined tree. Each i is answered independently — the added edge is removed before the next one.
Return an array answer of length n where answer[i] is the maximum possible number of targets of node i.
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: Node 0 already reaches all 5 nodes of its tree within 2 edges; joining it to node 0 of the second tree adds the 4 nodes within 1 edge of that node.
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: The new edge costs one step, so only the second tree's endpoint itself can be reached.
Example 3
Input: edges1 = [[0,1]], edges2 = [[0,1]], k = 0
Output: [1,1]
Explanation: With k = 0 the only target is the node itself; the second tree is out of reach.
Constraints
2 <= n, m <= 1000edges1.length == n - 1edges2.length == m - 1edges1[i].length == edges2[i].length == 2the inputs are valid trees0 <= k <= 1000
Hints for Maximize the Number of Target Nodes After Connecting Trees I
Hint 1
The new edge is one step long, so from
iyou can reach second-tree nodes withink - 1steps of the endpoint you connect to.Hint 2
That makes the two trees independent: the best endpoint in the second tree is the same for every
i— the node with the most nodes within distancek - 1.Hint 3
With at most 1000 nodes per tree, a BFS from every node (stopping at the distance limit) counts the nodes within reach. Connect
iitself to the best second-tree node:answer[i] = within1(i, k) + max within2(j, k - 1).
How to solve Maximize the Number of Target Nodes After Connecting Trees I
Joining i directly to some node j of the second tree is always best, since any other attachment point only lengthens the paths into the second tree. The answer splits into two independent counts: targets inside the first tree, plus the best second-tree node's count of nodes within k - 1.
Approach
- For every node of the first tree, BFS up to depth
kand count the nodes reached. - If
k == 0, the second tree contributes nothing. Otherwise BFS from every node of the second tree up to depthk - 1and take the maximum count. answer[i] = count1[i] + best2.
Why it works
Every path from i into the second tree crosses the new edge, which costs one step. Attaching that edge at i itself leaves k - 1 steps for the second tree; attaching it elsewhere in the first tree only leaves fewer. Inside the first tree the new edge is useless (it leads away). So both parts are maximised independently.
Complexity
- Time —
O(n² + m²) - Space —
O(n + m)
Pitfalls
- With
k = 0the second tree contributes 0, not 1 — reaching it takes one step. - The second tree's budget is
k - 1, notk. - Stop each BFS at the depth limit, or the counts include nodes that are too far.
Reference solution
Python
from typing import List
def maxTargetNodes(edges1: List[List[int]], edges2: List[List[int]], k: int) -> List[int]:
best = max(_within(edges2, k - 1))
return [x + best for x in _within(edges1, k)]
def _within(edges: List[List[int]], lim: int) -> List[int]:
n = len(edges) + 1
res = [0] * n
if lim < 0:
return res
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
for s in range(n):
dist = [-1] * n
dist[s] = 0
q = [s]
for u in q:
if dist[u] == lim:
continue
for v in adj[u]:
if dist[v] < 0:
dist[v] = dist[u] + 1
q.append(v)
res[s] = len(q)
return resJava
static int[] within(int[][] edges, int lim) {
int n = edges.length + 1;
int[] res = new int[n];
if (lim < 0) return res;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
int[] dist = new int[n], q = new int[n];
for (int s = 0; s < n; s++) {
Arrays.fill(dist, -1);
dist[s] = 0;
int tail = 0;
q[tail++] = s;
for (int h = 0; h < tail; h++) {
int u = q[h];
if (dist[u] == lim) continue;
for (int v : adj.get(u)) if (dist[v] < 0) { dist[v] = dist[u] + 1; q[tail++] = v; }
}
res[s] = tail;
}
return res;
}
public static int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {
int best = 0;
for (int x : within(edges2, k - 1)) best = Math.max(best, x);
int[] a = within(edges1, k);
for (int i = 0; i < a.length; i++) a[i] += best;
return a;
}C++
vector<int> within(vector<vector<int>>& edges, int lim) {
int n = edges.size() + 1;
vector<int> res(n, 0);
if (lim < 0) return res;
vector<vector<int>> adj(n);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
vector<int> dist(n), q(n);
for (int s = 0; s < n; s++) {
fill(dist.begin(), dist.end(), -1);
dist[s] = 0;
int tail = 0;
q[tail++] = s;
for (int h = 0; h < tail; h++) {
int u = q[h];
if (dist[u] == lim) continue;
for (int v : adj[u]) if (dist[v] < 0) { dist[v] = dist[u] + 1; q[tail++] = v; }
}
res[s] = tail;
}
return res;
}
vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {
vector<int> b = within(edges2, k - 1);
int best = *max_element(b.begin(), b.end());
vector<int> a = within(edges1, k);
for (int& x : a) x += best;
return a;
}JavaScript
var maxTargetNodes = function(edges1, edges2, k) {
var b = within(edges2, k - 1), best = 0;
for (var i = 0; i < b.length; i++) if (b[i] > best) best = b[i];
var a = within(edges1, k), ans = [];
for (var j = 0; j < a.length; j++) ans.push(a[j] + best);
return ans;
};
var within = function(edges, lim) {
var n = edges.length + 1, res = [], adj = [], dist = [];
for (var i = 0; i < n; i++) { res.push(0); adj.push([]); dist.push(-1); }
if (lim < 0) return res;
for (var e = 0; e < edges.length; e++) {
adj[edges[e][0]].push(edges[e][1]);
adj[edges[e][1]].push(edges[e][0]);
}
for (var s = 0; s < n; s++) {
for (var z = 0; z < n; z++) dist[z] = -1;
dist[s] = 0;
var q = [s];
for (var h = 0; h < q.length; h++) {
var u = q[h];
if (dist[u] === lim) continue;
for (var j = 0; j < adj[u].length; j++) {
var v = adj[u][j];
if (dist[v] < 0) { dist[v] = dist[u] + 1; q.push(v); }
}
}
res[s] = q.length;
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)