Maximize the Number of Target Nodes After Connecting Trees I - 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] = [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.

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.

Input & Output

Example 1 — Basic Tree Connection

$ Input: edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1]], k = 3

› Output: [6,3,6,3,3]

💡 Note: Tree1 has 5 nodes (0-4), Tree2 has 2 nodes (0-1). With k=3, connecting the trees optimally allows each node to reach different numbers of target nodes. Node 0 and 2 can reach 6 nodes total when connected optimally.

Example 2 — Small Trees

$ Input: edges1 = [[0,1]], edges2 = [[0,1]], k = 1

› Output: [3,3]

💡 Note: Each tree has 2 nodes. With k=1, each node in tree1 can reach at most 3 nodes total (itself + 1 neighbor in tree1 + 1 reachable node in tree2 through optimal bridge).

Example 3 — Limited Distance

$ Input: edges1 = [[0,1],[1,2]], edges2 = [[0,1]], k = 1

› Output: [3,4,3]

💡 Note: With k=1, middle node 1 can reach more nodes (4 total) since it's centrally located in tree1, while nodes 0 and 2 can reach 3 nodes each.

Constraints

1 ≤ n, m ≤ 1000
edges1.length == n - 1
edges2.length == m - 1
0 ≤ edges1[i][0], edges1[i][1] < n
0 ≤ edges2[i][0], edges2[i][1] < m
1 ≤ k ≤ 1000

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12

The key insight is to precompute reachable node counts for each tree separately, then find the optimal bridge connection. The optimized approach runs in O((n+m)²) time and O(n+m) space by avoiding redundant distance calculations.

Common Approaches

✓ Backtracking

⏱️ Time: N/A Space: N/A

Brute Force - Try All Connections

⏱️ Time: O(n²m²k) Space: O(n + m)

For each node in the first tree, try connecting every possible pair of nodes between the two trees, then use BFS to count all nodes within distance k from that node.

Optimized - Precompute Distances

⏱️ Time: O((n + m) × (n + m)) Space: O((n + m)²)

First calculate how many nodes each node can reach within k steps in its own tree. Then for each node in tree1, find the best connection point in tree2 that maximizes additional reachable nodes.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 1000
#define MAX_QUEUE 2000

int adj1[MAX_NODES][MAX_NODES];
int adj1_size[MAX_NODES];
int adj2[MAX_NODES][MAX_NODES];
int adj2_size[MAX_NODES];
int visited[MAX_NODES + MAX_NODES];
int queue[MAX_QUEUE];
int dist[MAX_NODES + MAX_NODES];

int bfs(int start, int n1, int n2, int bridge1, int bridge2, int k) {
    int front = 0, rear = 0;
    
    for (int i = 0; i < n1 + n2; i++) {
        visited[i] = 0;
        dist[i] = -1;
    }
    
    queue[rear++] = start;
    visited[start] = 1;
    dist[start] = 0;
    
    int count = 1;
    
    while (front < rear) {
        int curr = queue[front++];
        
        if (curr < n1) {
            // Node in tree1
            for (int i = 0; i < adj1_size[curr]; i++) {
                int next = adj1[curr][i];
                if (!visited[next] && dist[curr] + 1 <= k) {
                    visited[next] = 1;
                    dist[next] = dist[curr] + 1;
                    queue[rear++] = next;
                    count++;
                }
            }
            
            // Check bridge connection
            if (curr == bridge1 && !visited[n1 + bridge2] && dist[curr] + 1 <= k) {
                visited[n1 + bridge2] = 1;
                dist[n1 + bridge2] = dist[curr] + 1;
                queue[rear++] = n1 + bridge2;
                count++;
            }
        } else {
            // Node in tree2
            int curr2 = curr - n1;
            for (int i = 0; i < adj2_size[curr2]; i++) {
                int next = n1 + adj2[curr2][i];
                if (!visited[next] && dist[curr] + 1 <= k) {
                    visited[next] = 1;
                    dist[next] = dist[curr] + 1;
                    queue[rear++] = next;
                    count++;
                }
            }
            
            // Check bridge connection
            if (curr2 == bridge2 && !visited[bridge1] && dist[curr] + 1 <= k) {
                visited[bridge1] = 1;
                dist[bridge1] = dist[curr] + 1;
                queue[rear++] = bridge1;
                count++;
            }
        }
    }
    
    return count;
}

int* solve(int** edges1, int edges1Size, int** edges2, int edges2Size, int k, int* returnSize) {
    int n1 = edges1Size + 1;
    int n2 = edges2Size + 1;
    
    // Initialize adjacency lists
    for (int i = 0; i < n1; i++) adj1_size[i] = 0;
    for (int i = 0; i < n2; i++) adj2_size[i] = 0;
    
    // Build adjacency list for tree1
    for (int i = 0; i < edges1Size; i++) {
        int u = edges1[i][0], v = edges1[i][1];
        adj1[u][adj1_size[u]++] = v;
        adj1[v][adj1_size[v]++] = u;
    }
    
    // Build adjacency list for tree2
    for (int i = 0; i < edges2Size; i++) {
        int u = edges2[i][0], v = edges2[i][1];
        adj2[u][adj2_size[u]++] = v;
        adj2[v][adj2_size[v]++] = u;
    }
    
    int* result = (int*)malloc(n1 * sizeof(int));
    *returnSize = n1;
    
    // For each node in tree1
    for (int start = 0; start < n1; start++) {
        int maxNodes = 0;
        
        // Try all possible bridge connections
        for (int bridge1 = 0; bridge1 < n1; bridge1++) {
            for (int bridge2 = 0; bridge2 < n2; bridge2++) {
                int reachable = bfs(start, n1, n2, bridge1, bridge2, k);
                if (reachable > maxNodes) {
                    maxNodes = reachable;
                }
            }
        }
        
        result[start] = maxNodes;
    }
    
    return result;
}

int parseArray(char* str, int*** edges, int* edgeCount) {
    *edgeCount = 0;
    if (str[1] == ']') {
        *edges = NULL;
        return 0;
    }
    
    // Count edges
    for (int i = 0; str[i]; i++) {
        if (str[i] == '[' && i > 0) (*edgeCount)++;
    }
    
    *edges = (int**)malloc(*edgeCount * sizeof(int*));
    for (int i = 0; i < *edgeCount; i++) {
        (*edges)[i] = (int*)malloc(2 * sizeof(int));
    }
    
    int edgeIdx = 0;
    char* ptr = str + 1;
    
    while (*ptr && edgeIdx < *edgeCount) {
        if (*ptr == '[') {
            ptr++;
            (*edges)[edgeIdx][0] = strtol(ptr, &ptr, 10);
            ptr++; // skip comma
            (*edges)[edgeIdx][1] = strtol(ptr, &ptr, 10);
            edgeIdx++;
        }
        ptr++;
    }
    
    return *edgeCount;
}

int main() {
    char line1[10000], line2[10000], line3[100];
    
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    fgets(line3, sizeof(line3), stdin);
    
    // Remove newlines
    line1[strcspn(line1, "\n")] = 0;
    line2[strcspn(line2, "\n")] = 0;
    line3[strcspn(line3, "\n")] = 0;
    
    int** edges1;
    int** edges2;
    int edges1Size, edges2Size;
    int k = strtol(line3, NULL, 10);
    
    parseArray(line1, &edges1, &edges1Size);
    parseArray(line2, &edges2, &edges2Size);
    
    int returnSize;
    int* result = solve(edges1, edges1Size, edges2, edges2Size, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    // Cleanup
    for (int i = 0; i < edges1Size; i++) free(edges1[i]);
    for (int i = 0; i < edges2Size; i++) free(edges2[i]);
    if (edges1) free(edges1);
    if (edges2) free(edges2);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen