Maximize the Number of Target Nodes After Connecting Trees I

Medium
1728.

Maximize the Number of Target Nodes After Connecting Trees I

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.

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 <= 1000
  • edges1.length == n - 1
  • edges2.length == m - 1
  • edges1[i].length == edges2[i].length == 2
  • the inputs are valid trees
  • 0 <= k <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} edges1
 * @param {number[][]} edges2
 * @param {number} k
 * @return {number[]}
 */
var maxTargetNodes = function(edges1, edges2, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • edges1.length == n - 1
  • edges2.length == m - 1
  • edges1[i].length == edges2[i].length == 2
  • the inputs are valid trees
  • 0 <= k <= 1000

Hints for Maximize the Number of Target Nodes After Connecting Trees I

  1. Hint 1

    The new edge is one step long, so from i you can reach second-tree nodes within k - 1 steps of the endpoint you connect to.

  2. 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 distance k - 1.

  3. 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 i itself 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

  1. For every node of the first tree, BFS up to depth k and count the nodes reached.
  2. If k == 0, the second tree contributes nothing. Otherwise BFS from every node of the second tree up to depth k - 1 and take the maximum count.
  3. 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 = 0 the second tree contributes 0, not 1 — reaching it takes one step.
  • The second tree's budget is k - 1, not k.
  • 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 res

Java

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)